Application of Upper and Lower Bounds for the Domination Number to Vizing’s Conjecture

Abstract

Vizing conjectured that $\gamma (G)\gamma (H)\le \gamma (G\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}H)$ for all graphs $G$ and $H$, where $\gamma (G)$ denotes the domination number of $G$ and $G\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}H$ is the Cartesian product of $G$ and $H$. We prove that if $G$ and $H$ are $\delta$-regular, then, with only a few possible exceptions, Vizing’s conjecture holds. We also prove that if $\delta (G),\mathrm{\Delta }(G),\delta (H)$, and $\mathrm{\Delta }(H)$ are in a certain range, then Vizing’s conjecture holds. In particular, we show that for graphs of order at most $n$ with minimum degrees at least $\sqrt{n}\ln n$, the conjecture holds.