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

For a graph, G, and a vertex v is an element of V (G), let N vertical bar v vertical bar be the set of vertices adjacent to and including v. A set D subset of V (G) is a (vertex) identifying code if for any two distinct vertices v(1), v(2) is an element of V (G), the vertex sets N vertical bar v(1)vertical bar boolean AND D and N vertical bar v(2)vertical bar boolean AND 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 3/7 approximate to 0.428571, and this remains the best known upper bound. Until now, the best known lower bound was 12/29 approximate to 0.413793 and was proved by Cranston and Yu in 2009. We present three new codes with a density of 3/7, and we improve the lower bound to 5/1 approximate to 0.416667. (C) 2013 Elsevier B.V. All rights reserved.