New bounds on the minimum density of an identifying code for the infinite hexagonal grid ?
For a graph, G G , and a vertex v?V(G) v ? V ( G ) , let N[v] N [ v ] be the set of vertices adjacent to and including v v . A set D?V(G) D ? V ( G ) is a (vertex) identifying code if for any two distinct vertices v1,v2?V(G) v 1 , v 2 ? V ( G ) , the vertex sets N[v1]?D N [ v 1 ] ? D and N[v2]?D N [ v 2 ] ? 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 ? 0.428571 , and this remains the best known upper bound. Until now, the best known lower bound was 12 29 ? 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 12 ? 0.416667 .
identifying code infinite hexagonal grid discharging method