Vizing's Conjecture for Almost All Pairs of Graphs

Abstract

For any graph $G=(V,E)$, a subset $S\subseteq V$ $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)\ge \gamma (G)\gamma (H)$ where $\square$ stands for the Cartesian product of graphs. In this note, we prove that if $\left|G\right|\ge \gamma (G)\gamma (H)$ and $\left|H\right|\ge \gamma (G)\gamma (H)$, then the conjecture holds. This result quickly implies Vizing's conjecture for almost all pairs of graphs $G,H$ with $\left|G\right|\ge \left|H\right|$, satisfying $\left|G\right|\le q^{\frac{|H|}{{\log }_q|H|}}$ for $q=\frac{1}{1-p}$ and $p$ the edge probability of the Erdős-Rényi random graph.

5 pages