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

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 (l,i,j)-covers. (C) 2002 Elsevier Science B.V. All rights reserved.