Watching Systems in the King Grid



: Auger D, Honkala I

Publisher: SPRINGER JAPAN KK

: 2013

: Graphs and Combinatorics

: GRAPHS AND COMBINATORICS

: GRAPH COMBINATOR

: 3

: 29

: 3

: 333

: 347

: 15

: 0911-0119

DOI: https://doi.org/10.1007/s00373-011-1124-0


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.



Last updated on 2024-26-11 at 21:55