A New Lower Bound on the Density of Vertex Identifying Codes for the Infinite Hexagonal Grid

Given a graph G, an identifying code D subset of V(G) is a vertex set such that for any two distinct vertices v(1), v(2) is an element of V(G), the sets N[v(1)] boolean AND D and N[v(2)] boolean AND D are distinct and nonempty (here N[v] denotes a vertex v and its neighbors). We study the case when G is the infinite hexagonal grid H.Cohen et.al. constructed two identifying codes for H with density 3/7 and proved that any identifying code for H must have density at least 16/39 approximate to 0.410256. Both their upper and lower bounds were best known until now. Here we prove a lower bound of 12/29 approximate to 0.413793