Optimal Lower Bound for 2-Identifying Codes in the Hexagonal Grid

Abstract

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.