Bounds for Codes Identifying Vertices in the Hexagonal Grid
Gérard Cohen, Iiro S. Honkala, Antoine C. Lobstein, Gilles Zémor · SIAM Journal on Discrete Mathematics · 2000
In an undirected graph G=(V,E), a subset $C \subseteq V$ is called an identifying code if the sets $B_1(v) \cap C$ consisting of all elements of C within distance one from the vertex v are nonempty and different. We take G to be the infinite hexagonal grid and show that the density of any identifying code is at least 16/39 and that there is an identifying code of density 3/7.