A brief, simple proof of Vizing's conjecture

Details A brief, simple proof of Vizing's conjecture A brief, simple proof of Vizing's conjecture

2011-09-04

arxiv.org/abs/1109.0707v2

Mathematics

Combinatorics

This paper has been withdrawn by the author due to a problem with the "label exchange"

Scientific paper

For any graph $G=(V,E)$, a subset $S\subseteq V$ \emph{dominates} $G$ if all vertices are contained in the closed neighborhood of $S$, that is $N[S]=V$. The minimum cardinality over all such $S$ is called the domination number, written $\gamma(G)$. In 1963, V.G. Vizing conjectured that $\gamma(G \square H) \geq \gamma(G)\gamma(H)$ where $\square$ stands for the Cartesian product of graphs. In this note, we prove the conjecture.

Affiliated with

Also associated with

No associations

Rating

A brief, simple proof of Vizing's conjecture does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A brief, simple proof of Vizing's conjecture, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A brief, simple proof of Vizing's conjecture will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-109128