New lower bound for 2-identifying code in the square grid

An rr-identifying code in a graph G=(V,E)G=(V,E) is a subset C⊆VC⊆V such that for each u∈Vu∈V the intersection of CC and the ball of radius rr centered at uu is nonempty and unique. Previously, rr-identifying codes have been studied in various grids. In particular, it has been shown that there exists a 22-identifying code in the square grid with density 5/29≈0.1725/29≈0.172 and that there are no 22-identifying codes with density smaller than 3/20=0.153/20=0.15. Recently, the lower bound has been improved to 6/37≈0.1626/37≈0.162 by Martin and Stanton (2010)  [11]. In this paper, we further improve the lower bound by showing that there are no 22-identifying codes in the square grid with density smaller than 6/35≈0.1716/35≈0.171.