On Codes Identifying Vertices in the Two-Dimensional Square Lattice with Diagonals
IEEE Transactions on Computers, vol. 50, pp. 174-176, February 2001.
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. Fault diagnosis of multiprocessor systems motivates the following graph-theoretic definition. A subset C of points in an undirected graph G=(V, E) is called an identifying code if the sets B(v) $\cap$ C consisting of all elements of C within distance one from the vertex v are different. We also require that the sets B(v) $\cap$ C are all nonempty. We take G to be the infinite square lattice with diagonals and show that the density of the smallest identifying code is at least 2/9 and at most 4/17.