Inequality Related to Vizing's Conjecture

W. Edwin Clark, Stephen Suen

Abstract


Let $\gamma(G)$ denote the domination number of a graph $G$ and let $G\square H$ denote the Cartesian product of graphs $G$ and $H$. We prove that $\gamma(G)\gamma(H) \le 2 \gamma(G\square H)$ for all simple graphs $G$ and $H$.


Full Text: PDF