New bounds on the minimum density of an identifying code for the infinite hexagonal grid

For a graph, GG, and a vertex v∈V(G)v∈V(G), let N[v]N[v] be the set of vertices adjacent to and including vv. A set D⊆V(G)D⊆V(G) is a (vertex) identifying code if for any two distinct vertices v1,v2∈V(G)v1,v2∈V(G), the vertex sets N[v1]∩DN[v1]∩D and N[v2]∩DN[v2]∩D are distinct and non-empty. We consider the minimum density of a vertex identifying code for the infinite hexagonal grid. In 2000, Cohen et al. constructed two codes with a density of 37≈0.428571, and this remains the best known upper bound. Until now, the best known lower bound was 1229≈0.413793 and was proved by Cranston and Yu in 2009. We present three new codes with a density of 37, and we improve the lower bound to 512≈0.416667.