%0 Journal Article
%T A brief, simple proof of Vizing's conjecture
%A Elliot Krop
%J Mathematics
%D 2011
%I arXiv
%X 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.
%U http://arxiv.org/abs/1109.0707v2