Codes for identification in the king lattice
: Honkala I, Laihonen T
Publisher: SPRINGER-VERLAG TOKYO
: 2003
: Graphs and Combinatorics
: GRAPHS AND COMBINATORICS
: GRAPH COMBINATOR
: 19
: 4
: 505
: 516
: 12
: 0911-0119
DOI: https://doi.org/10.1007/s00373-003-0531-2(external)
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.