Domination number of the cross product of paths (Q1293195)

The domination number, \(\gamma(G)\), of an (undirected simple) graph \(G=(V(G),E(G))\) is the minimum cardinality of a set \(D\) of vertices such that every vertex in \(V(G)\) is adjacent to at least one vertex in \(D\). Given two graphs \(G\), \(H\), the square product \(G\square H\) has \(V(G\square H)=V(G)\times V(H)\), and \(((u,u'),(v,v'))\in E(G\square H)\) iff \(u=v\) and \((u',v')\in E(H)\); or \((u,v)\in E(G)\) and \(u'=v'\). The cross product \(G\times H\) also has vertex-set \(V(G)\times V(H)\); \(((u,u'),(v,v'))\in E(G\times H)\) iff \((u,v)\in E(G)\) and \((u',v')\in E(H)\). \(P_\ell\) denotes a path with \(\ell\) vertices; the square product of two paths is called a complete grid. From the authors' introduction: ``In Section (2) we give the domination numbers of \(P_k\times P_n\) for \(k\leq 8\), which is a special subgraph of a complete grid graph. In Section (3) we give an algorithm for determining the domination number of the cross product of two paths; we determine \(\gamma(P_n\times P_9)\) for \(n\geq 8\); we give some close bounds for \(\gamma(P_n\times P_{10})\), \(\gamma(P_n\times P_{11})\) and \(\gamma(P_n\times P_{13})\); and finally we obtain the exact values of \(\gamma(P_n\times P_{k})\), for \(10\leq k\leq 33\) and \(1\leq n\leq 40\). In Section (4) we explain how this last result can be extended to determine \(\gamma(P_n\times P_{k})\) for all \(k\) and \(n\) greater than or equal to 14.'' In Section (5) it is conjectured that ``For sufficiently large \(k\) and \(n\), \(\gamma(P_n\square P_{k})=\left\lfloor\frac{(k+2)(n+2)}5\right\rfloor-4\),'' and stated that ``Using a computer, the first values for which this conjecture is true are \(k=16\) and \(16\leq n\leq 50\)''.