On multiple coverings of the infinite rectangular grid with balls of constant radius (Q1398253)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On multiple coverings of the infinite rectangular grid with balls of constant radius |
scientific article |
Statements
On multiple coverings of the infinite rectangular grid with balls of constant radius (English)
0 references
29 July 2003
0 references
In this paper the coverings of graphs with balls of constant radius satisfying a special multiplicity condition are considered. 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\backslash S\) belongs to exactly \(j\) balls of radius \(t\) centered at elements of \(S\). For the infinite rectangular grid, it is shown 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\) it is proved that all \((t,i,j)\)-covers are the unions of the diagonals periodically located in the grid. Also, the description of all \((1,i,j)\)-covers is proposed in the paper.
0 references
multiple coverings
0 references
infinite rectangular grid
0 references
perfect coverings
0 references
covering codes
0 references
isotropic (distributive) colorings
0 references