Some results on domination number of products of graphs (Q1387527)

A dominating set in a graph \(G\) is a subset \(D\) of the vertex set of \(G\) with the property that each vertex of \(G\) either is in \(D\), or is adjacent to a vertex of \(D\). The minimum number of vertices of a dominating set in \(G\) is the domination number \(\gamma (G)\) of \(G\). The minimum number of vertices of a dominating set in \(G\) which induces a connected subgraph of \(G\) is the connected domination number \(\gamma_c(G)\) of \(G\). A conjecture of V. G. Vizing says that for the Cartesian product \(G\times H\) of graphs \(G\) and \(H\) the inequality \(\gamma (G\times H) \geq\gamma (G)\cdot \gamma (H)\) holds. The main theorem of the paper states that this inequality holds in the case when \(\gamma (H)\neq \gamma_c (H)\). In particular, it holds if \(H\) is a path or a circuit. Further a lower bound and an upper bound for the domination number of the Cartesian product of two paths are found, both in terms of their lengths.