On domination numbers of Cartesian products of paths (Q1382283)

The \(r\)-domination number \(\gamma_r(G)\) of a graph \(G\) is studied. A subset \(D\) of the vertex set \(V(G)\) of \(G\) is called \(r\)-dominating for a positive integer \(r\), if for each \(x\in V(G)-D\) there exists a vertex \(y\in D\) whose distance from \(x\) in \(G\) is at most \(r\). The minimum number of vertices of an \(r\)-dominating set in \(G\) is the \(r\)-domination number \(\gamma_r(G)\) of \(G\). The Cartesian product of two graphs \(G,H\) is the graph \(G\square H\) whose vertex set \(V(G \square H)\) is \(V(G) \times V(H)\) and in which two vertices \((u,u')\), \((v,v')\) are adjacent if and only if either \(u\) and \(v\) are adjacent in \(G\) and \(u'=v'\), or \(u=v\) and \(u'\) and \(v'\) are adjacent in \(H\). This concept may be extended to an arbitrary number of factors. The first theorem of the paper gives an upper bound for the \(r\)-domination number of the Cartesian product of two paths in terms of \(r\) and of the lengths of these paths. The second theorem gives such an upper bound for the Cartesian product of an arbitrary number of paths.