New lower bound for 2-identifying code in the square 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 nonempty 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 square grid with density $5/29\approx 0.172$ and that there are no 2-identifying codes with density smaller than $3/20=0.15$. Recently, the lower bound has been improved to $6/37\approx 0.162$ by Martin and Stanton (2010). In this paper, we further improve the lower bound by showing that there are no 2-identifying codes in the square grid with density smaller than $6/35\approx 0.171$.

arXiv commentarXiv admin note: substantial text overlap with arXiv:1202.0670