Bounds for Codes Identifying Vertices in the Hexagonal GridSIAM Journal on Discrete Mathematics, Vol. 13, No. 4, pp. 492-504, 2000.
Gérard COHEN (*), Iiro HONKALA (#), Antoine LOBSTEIN (*), Gilles ZÉMOR (*)
(*) Centre National de la Recherche Scientifique
Ecole Nationale Supérieure des Télécommunications
46 rue Barrault, 75634 Paris cédex 13, France
(#) Department of Mathematics
University of Turku
20014 Turku, Finland
Abstract. In an undirected graph G=(V, E) a subset C of vertices is called an identifying code if the sets B1(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.