Optimal lower bound for 2-identifying codes in the hexagonal grid (Q456287)

Summary: 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 \textit{R. Martin} and \textit{B. Stanton} [Electron. J. Comb. 17, No. 1, Research Paper R122, 16 p., electronic only (2010; Zbl 1272.05161)]. 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.