On the domination number of cross products of graphs (Q1901047)

The cross product \(G\otimes G'\) of two graphs \(G\), \(G'\) is the graph whose vertex set is the Cartesian product of the vertex sets of \(G\) and \(G'\) and in which two vertices \((u, u')\), \((v, v')\) are adjacent if and only if \(u\), \(v\) are adjacent in \(G\) and \(u'\), \(v'\) are adjacent in \(G'\). A subset \(D\) of the vertex set \(V(G)\) of a graph \(G\) is called dominating in \(G\), if for each \(x\in V(G)- D\) there exists a vertex \(y\in D\) adjacent to \(x\). The minimum number of vertices of a dominating set in \(G\) is called the domination number of \(G\). In the paper, the domination number of the cross product \(P_n\otimes P^c_k\) of a path \(P_n\) of length \(n\) with the complement \(P^c_k\) of a path of length \(k\) is found for all values of \(n\) and \(k\). Some corollaries are stated and a conjecture is expressed saying that \(\gamma(G\otimes H)\geq \gamma(G) \gamma(H)\), where \(\gamma\) denotes the domination number.