On Identifying Codes
Proceedings of DIMACS Workshop on Codes and Association Schemes '99, vol. 56, pp. 97-109, January 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 a connected undirected graph G=(V, E) is called an r-identifying code, if the sets consisting of all elements of C within distance r from the vertex v are nonempty and different for all v in V. We show that no nontrivial perfect r-identifying codes exist for r>1, and study how small the density of an r-identifying code can be in certain infinite graphs. We also show that the problem of existence of a 1-identifying code of size at most k in a graph is NP-complete.