On multiple coverings of the infinite rectangular grid with balls of constant radius (Q1398253): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Removed claim: reviewed by (P1447): Item:Q190560
RedirectionBot (talk | contribs)
Changed an Item
Property / reviewed by
 
Property / reviewed by: Ioan Tomescu / rank
 
Normal rank

Revision as of 11:05, 10 February 2024

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