A1 Refereed original research article in a scientific journal
Watching Systems in the King Grid
Authors: Auger D, Honkala I
Publisher: SPRINGER JAPAN KK
Publication year: 2013
Journal: Graphs and Combinatorics
Journal name in source: GRAPHS AND COMBINATORICS
Journal acronym: GRAPH COMBINATOR
Number in series: 3
Volume: 29
Issue: 3
First page : 333
Last page: 347
Number of pages: 15
ISSN: 0911-0119
DOI: https://doi.org/10.1007/s00373-011-1124-0
Abstract
We consider the infinite King grid where we investigate properties of watching systems, an extension of the notion of identifying code recently introduced by Auger et al. (Discret. Appl. Math., 2011). The latter were extensively studied in the infinite King grid and we compare our results with those holding for (r, a parts per thousand currency signa"")-identifying codes. We prove that for r = 1 and a"" = 1, the minimal density of an identifying code, known to be also holds for watching systems; however, when r is large we give an asymptotic equivalence of the optimal density of watching systems which is much better than identifying codes'. Turning to the case r = 1 and a"" a parts per thousand yen 1, we prove that in a certain sense when a"" a parts per thousand yen 6 the best watching systems in the infinite King grid are trivial, but that this is not the case when a"" a parts per thousand currency sign 4.
We consider the infinite King grid where we investigate properties of watching systems, an extension of the notion of identifying code recently introduced by Auger et al. (Discret. Appl. Math., 2011). The latter were extensively studied in the infinite King grid and we compare our results with those holding for (r, a parts per thousand currency signa"")-identifying codes. We prove that for r = 1 and a"" = 1, the minimal density of an identifying code, known to be also holds for watching systems; however, when r is large we give an asymptotic equivalence of the optimal density of watching systems which is much better than identifying codes'. Turning to the case r = 1 and a"" a parts per thousand yen 1, we prove that in a certain sense when a"" a parts per thousand yen 6 the best watching systems in the infinite King grid are trivial, but that this is not the case when a"" a parts per thousand currency sign 4.
UTU Research Portal