On multiple coverings of the infinite rectangular grid with balls of constant radius
type: Item
instance of: scholarly article
title: On multiple coverings of the infinite rectangular grid with balls of constant radius
zbMATH Open document ID: 1018.05080
DOI: 10.1016/S0012-365X(02)00744-6
author: Maria Axenovich
published in: Discrete Mathematics
publication date: 2003-07-29T00:00:00Z
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.
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1956029
zbMATH Keywords: multiple coverings
zbMATH Keywords: infinite rectangular grid
zbMATH Keywords: perfect coverings
zbMATH Keywords: covering codes
zbMATH Keywords: isotropic (distributive) colorings
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1956029