A1 Refereed original research article in a scientific journal
Codes for identification in the king lattice
Authors: Honkala I, Laihonen T
Publisher: SPRINGER-VERLAG TOKYO
Publication year: 2003
Journal: Graphs and Combinatorics
Journal name in source: GRAPHS AND COMBINATORICS
Journal acronym: GRAPH COMBINATOR
Volume: 19
Issue: 4
First page : 505
Last page: 516
Number of pages: 12
ISSN: 0911-0119
DOI: https://doi.org/10.1007/s00373-003-0531-2
Abstract
Let G=(V, E) be an undirected graph and C a subset of vertices. If the sets B-r(F)boolean ANDC are distinct for all subsets Fsubset ofV with at most k elements, then C is called an (r,less than or equal tok)-identifying code in G. Here B-r(F) denotes the set of all vertices that are within distance r from at least one vertex in F. We consider the two-dimensional square lattice with diagonals (the king lattice). We show that the optimal density of an (r,less than or equal to2)-identifying code is 1/4 for all rgreater than or equal to3. For r=1,2, we give constructions with densities 3/7 and 3/10, and we prove the lower bounds 9/22 and 31/120, respectively.
Let G=(V, E) be an undirected graph and C a subset of vertices. If the sets B-r(F)boolean ANDC are distinct for all subsets Fsubset ofV with at most k elements, then C is called an (r,less than or equal tok)-identifying code in G. Here B-r(F) denotes the set of all vertices that are within distance r from at least one vertex in F. We consider the two-dimensional square lattice with diagonals (the king lattice). We show that the optimal density of an (r,less than or equal to2)-identifying code is 1/4 for all rgreater than or equal to3. For r=1,2, we give constructions with densities 3/7 and 3/10, and we prove the lower bounds 9/22 and 31/120, respectively.
UTU Research Portal