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

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

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.

Recommendations

Cited in

(17)

This page was built for publication: On multiple coverings of the infinite rectangular grid with balls of constant radius

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1398253)