An Improvement on Vizing's Conjecture

Abstract

Let $\gamma (G)$ denote the domination number of a graph $G$. A {\it Roman domination function} of a graph $G$ is a function $f:V\to \{0,1,2\}$ such that every vertex with 0 has a neighbor with 2. The {\it Roman domination number} ${\gamma }_R(G)$ is the minimum of $f(V(G))={\Sigma }_{v\in V}f(v)$ over all such functions. Let $G\square H$ denote the Cartesian product of graphs $G$ and $H$. We prove that $\gamma (G)\gamma (H)\le {\gamma }_R(G\square H)$ for all simple graphs $G$ and $H$, which is an improvement of $\gamma (G)\gamma (H)\le 2\gamma (G\square H)$ given by Clark and Suen \cite{CS}, since $\gamma (G\square H)\le {\gamma }_R(G\square H)\le 2\gamma (G\square H)$.

4 pages