Distance-2 domatic numbers of grid graphs (Q2799858)

This paper deals with distance-2 domatic numbers of grid graphs. A finite grid graph \(G_{m,n}\) is defined as the Cartesian product of paths \(P_n\) and \(P_m\). The infinite grid graph \(G_{\infty,\infty}\) is defined as the Cartesian product of two infinite paths. A vertex \(v\) in a graph \(G\) distance-2 dominates vertex \(u\) if the distance \(d(u,v)\leq 2\). A distance-2 dominating set is a set \(D\) of vertices that distance-2 dominate all vertices in \(V( G)\). A distance-2 domatic partition is a partition of \(V(G)\) into distance-2 dominating sets. The maximum number of sets in a distance-2 domatic partition is the distance-2 domatic number \(d_{\leq 2}(G)\).NEWLINENEWLINEThe values \(d_{\leq 2}(G_{m,n})\), where \(m\leq n\), are separately found for values \(m\in\{2,3,4,5\}\). Then, it is proved that \(d_{\leq 2}(G_{m,n})=6\) for all \(n\geq3\) and \(m\geq6\). At the end of the paper, the authors prove that \(d_{\leq 2}(G_{\infty,\infty})\) is equal to 13.