Watching Systems in the King Grid

Autor: David Auger, Iiro S. Honkala
Rok vydání: 2012
Předmět:
Zdroj: Graphs and Combinatorics. 29:333-347
ISSN: 1435-5914
0911-0119
DOI: 10.1007/s00373-011-1124-0
Popis: 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, ≤l)-identifying codes. We prove that for r = 1 and l = 1, the minimal density of an identifying code, known to be $${\frac{2}{9},}$$ 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 l ? 1, we prove that in a certain sense when l ? 6 the best watching systems in the infinite King grid are trivial, but that this is not the case when l ≤ 4.
Databáze: OpenAIRE
Externí odkaz: