On the domination number of the cartesian product of the path graph and any pair of graphs

Abstract

It is known that for any graph $G,$ $\gamma (G\square P_2)\ge \gamma (G)$ where $\gamma$ stands for the domination number, $\square$ for the cartesian product and $P_2$ is the path graph on two vertices. In an attempt to prove Vizing's conjecture, Clark and Suen proved in $2000$ that $\gamma (X\square Y)\ge \frac{1}{2}\gamma (X)\gamma (Y)$ for any pair of graphs $X$ and $Y.$ Combining these two inequalities, we have $\gamma (X\square Y\square P_2)\ge \frac{1}{2}\gamma (X)\gamma (Y).$ In this paper, we use space projections to improve this lower bound and show that $\gamma (X\square Y\square P_2)\ge \frac{2}{3}\gamma (X)\gamma (Y)$ for any pair of graphs $X$ and $Y.$ In addition, we prove that $\gamma (X\square Y\square P_n)\ge c_n\gamma (X)\gamma (Y)\gamma (P_n),$ where $c_n$ is almost $\frac{3}{4}$ when $n$ is big enough.

Comments are welcome !