An improved bound in Vizing's conjecture

Abstract

A well-known conjecture of Vizing is that $\gamma (G\square H)\ge \gamma (G)\gamma (H)$ for any pair of graphs $G,H$, where $\gamma$ is the domination number and $G\square H$ is the Cartesian product of $G$ and $H$. Suen and Tarr, improving a result of Clark and Suen, showed $\gamma (G\square H)\ge \frac{1}{2}\gamma (G)\gamma (H)+\frac{1}{2}\min (\gamma (G),\gamma (H))$. We further improve their result by showing $\gamma (G\square H)\ge \frac{1}{2}\gamma (G)\gamma (H)+\frac{1}{2}\max (\gamma (G),\gamma (H)).$