On 2-limited packings of complete grid graphs

For a fixed integer t, a set of vertices B of a graph G is a t-limited packing of G provided that the closed neighbourhood of any vertex in G contains at most t elements of B. The size of a largest possible t-limited packing in G is denoted Lt(G) and is the t-limited packing number of G. In this paper, we investigate the 2-limited packing number of Cartesian products of paths. We show that for fixed k the difference L2(Pk□Pn)−L2(Pk□Pn−1) is eventually periodic as a function of n, and thereby give closed formulas for L2(Pk□Pn), k=1,2,…,5. The techniques we use are suitable for establishing other types of packing and domination numbers for Cartesian products of paths and, more generally, for graphs of the form H□Pn.