2011/10/05 by Cukierman, Ari, Yu, Gexin
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1110.1097
For a graph, G, and a vertex v ∈ V(G), let N[v] be the set of vertices adjacent to and including v. A set D ⊆ V(G) is a vertex identifying code if for any two distinct vertices v1, v2 ∈ V(G), the vertex sets N[v1] ∩ D and N[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 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.