A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Optimal lower bound for 2-identifying codes in the hexagonal grid
Tekijät: Junnila V, Laihonen T
Kustantaja: ELECTRONIC JOURNAL OF COMBINATORICS
Julkaisuvuosi: 2012
Journal: The Electronic Journal of Combinatorics
Tietokannassa oleva lehden nimi: ELECTRONIC JOURNAL OF COMBINATORICS
Lehden akronyymi: ELECTRON J COMB
Numero sarjassa: 2
Vuosikerta: 19
Numero: 2
Sivujen määrä: 16
ISSN: 1077-8926
Tiivistelmä
An r-identifying code in a graph G = (V, E) is a subset C subset of V such that for each u is an element of V the intersection of C and the ball of radius r centered at u is non-empty and unique. Previously, r-identifying codes have been studied in various grids. In particular, it has been shown that there exists a 2-identifying code in the hexagonal grid with density 4/19 and that there are no 2-identifying codes with density smaller than 2/11. Recently, the lower bound has been improved to 1/5 by Martin and Stanton (2010). In this paper, we prove that the 2-identifying code with density 4/19 is optimal, i.e. that there does not exist a 2-identifying code in the hexagonal grid with smaller density.
An r-identifying code in a graph G = (V, E) is a subset C subset of V such that for each u is an element of V the intersection of C and the ball of radius r centered at u is non-empty and unique. Previously, r-identifying codes have been studied in various grids. In particular, it has been shown that there exists a 2-identifying code in the hexagonal grid with density 4/19 and that there are no 2-identifying codes with density smaller than 2/11. Recently, the lower bound has been improved to 1/5 by Martin and Stanton (2010). In this paper, we prove that the 2-identifying code with density 4/19 is optimal, i.e. that there does not exist a 2-identifying code in the hexagonal grid with smaller density.
Turun yliopiston Tutkimustietojärjestelmän portaali