2023/12/14 by Omar Tout, Tout, Omar
Computer Science · #Advanced Graph Theory Research #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2312.09208
It is known that for any graph G, γ(G\square P2)≥ γ(G) where γ stands for the domination number, \square for the cartesian product and P2 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)≥ (1)/(2)γ(X)γ(Y) for any pair of graphs X and Y. Combining these two inequalities, we have γ(X\square Y\square P2)≥ (1)/(2)γ(X)γ(Y). In this paper, we use space projections to improve this lower bound and show that γ(X\square Y\square P2)≥ (2)/(3)γ(X)γ(Y) for any pair of graphs X and Y. In addition, we prove that γ(X\square Y\square Pn)≥ cnγ(X)γ(Y)γ(Pn), where cn is almost (3)/(4) when n is big enough.