On the domination number of the Cartesian product of the cycle of length \(n\) and any graph (Q869572): Difference between revisions

Let \(\gamma(G)\) denote the domination number of a graph \(G\) (the minimum cardinality of a set \(D\) of vertices such that every vertex outside \(D\) has a neighbor in \(D\)). The Cartesian product \(G\square H\) of two graphs \(G\) and \(H\) is the graph with vertex set \(V_G\times V_H\) and \((a,c)(b,d)\) is an edge of \(G\square H\) if \(c=d\) and \(ab\in E_G\), or \(a=b\) and \(cd\in E_H\). The cycle of length \(n\) is denoted by \(C_n\). Among others, the authors show that \(\gamma(C_n\square G)=\gamma(C_n)\gamma(G)\) implies \(n\equiv 1 \pmod 3\). They also characterize all graphs \(G\) satisfying \(\gamma(C_4\square G)=\gamma(C_4)\gamma(G)\).