

























It is known that for any graph $G,$ $γ(G\square P_2)\geq γ(G)$ where $γ$ 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 $γ(X\square Y)\geq \frac{1}{2}γ(X)γ(Y)$ for any pair of graphs $X$ and $Y.$ Combining these two inequalities, we have $γ(X\square Y\square P_2)\geq \frac{1}{2}γ(X)γ(Y).$ In this paper, we use space projections to improve this lower bound and show that $γ(X\square Y\square P_2)\geq \frac{2}{3}γ(X)γ(Y)$ for any pair of graphs $X$ and $Y.$ In addition, we prove that $γ(X\square Y\square P_{n})\geq c_nγ(X)γ(Y)γ(P_{n}),$ where $c_n$ is almost $\frac{3}{4}$ when $n$ is big enough.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。