On multiple coverings of the infinite rectangular grid with balls of constant radius Original Research Article

We consider the coverings of graphs with balls of constant radius satisfying special multiplicity condition. A (t,i,j)-cover of a graph G=(V,E) is a subset S of vertices, such that every element of S belongs to exactly i balls of radius t centered at elements of S and every element of V⧹S belongs to exactly j balls of radius t centered at elements of S. For the infinite rectangular grid, we show that in any (t,i,j)-cover, i and j differ by at most t+2 except for one degenerate case. Furthermore, for i and j satisfying |i−j|>4 we show that all (t,i,j)-covers are the unions of the diagonals periodically located in the grid. Also, we give the description of all (1,i,j)-covers.