A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Codes for identification in the king lattice
Tekijät: Honkala I, Laihonen T
Kustantaja: SPRINGER-VERLAG TOKYO
Julkaisuvuosi: 2003
Journal: Graphs and Combinatorics
Tietokannassa oleva lehden nimi: GRAPHS AND COMBINATORICS
Lehden akronyymi: GRAPH COMBINATOR
Vuosikerta: 19
Numero: 4
Aloitussivu: 505
Lopetussivu: 516
Sivujen määrä: 12
ISSN: 0911-0119
DOI: https://doi.org/10.1007/s00373-003-0531-2
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali