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

From MaRDI portal
Revision as of 03:12, 5 March 2024 by Import240304020342 (talk | contribs) (Set profile property.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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
    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
    0 references

    Identifiers