An $r$-identifying code in a graph $G = (V,E)$ is a subset $C \subseteq V$ such that for each $u \in 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.
@article{10_37236_2414,
author = {Ville Junnila and Tero Laihonen},
title = {Optimal lower bound for 2-identifying codes in the hexagonal grid},
journal = {The electronic journal of combinatorics},
year = {2012},
volume = {19},
number = {2},
doi = {10.37236/2414},
zbl = {1252.05177},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2414/}
}
TY - JOUR
AU - Ville Junnila
AU - Tero Laihonen
TI - Optimal lower bound for 2-identifying codes in the hexagonal grid
JO - The electronic journal of combinatorics
PY - 2012
VL - 19
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/2414/
DO - 10.37236/2414
ID - 10_37236_2414
ER -
%0 Journal Article
%A Ville Junnila
%A Tero Laihonen
%T Optimal lower bound for 2-identifying codes in the hexagonal grid
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/2414/
%R 10.37236/2414
%F 10_37236_2414
Ville Junnila; Tero Laihonen. Optimal lower bound for 2-identifying codes in the hexagonal grid. The electronic journal of combinatorics, Tome 19 (2012) no. 2. doi: 10.37236/2414
