The 2-packing number of 3-dimensional grids (Q2715958)

The closed neighbourhood of a vertex \(v\) in a graph \(G\) is the set consisting of \(v\) and of all vertices which are adjacent to \(v\) in \(G\). A 2-packing of \(G\) is a subset of the vertex set of \(G\) whose vertices have pairwise disjoint closed neighbourhoods. The maximum of vertices of a 2-packing of \(G\) is the 2-packing number \(P_2(G)\) of \(G\). An \(\ell \times m \times n\) grid (3-dimensional grid) is the Cartesian product \(P_{\ell} \times P_m \times P_n\), where \(P_{\ell}, P_m, P_n\) are paths having \(\ell , m, n\) vertices respectively. The 2-packing number of \(P_{\ell} \times P_m\times P_n\) is denoted by \(\alpha _{\ell ,m,n}\). The exact value of \(\alpha _{2,m,n}\) is determined for all \(m,n\). Further \(\alpha _{3,3,n}\), \(\alpha _{3,4,n}\), \(\alpha _{3,1,n}\), \(\alpha _{4,4,n}\), \(\alpha _{5,5,n}\) are found for all \(n\). Also some partial results are presented.