[en] Covering problems are traditional issues in mathematics. For instance, a natural covering problem in the n-dimensional euclidean space is to ask for the minimal number of identical spheres needed to cover a large volume. The same issues can be considered in graphs. The corresponding covering problem is to determine the minimal number of r-balls that can be placed in such a way that every vertex of the graph is contained in at least one of them. In this talk, we consider coverings that satisfy special multiplicity conditions, called (r,a,b)-covering codes. These codes generalizes the notion of perfect codes in graphs that correspond to tilings of the graph with r-balls. We focus our attention on the multidimensional infinite grid and discuss the periodicity of (r,a,b)-codes in this case. Finally, for the dimension 2, we determine the possible values of the constant a and b.
Disciplines :
Mathematics
Author, co-author :
Vandomme, Elise ; Université de Liège > Département de mathématique > Mathématiques discrètes