Electronic Notes in Discrete Mathematics, Vol. 22, pp. 491-495, 2005.
Irène CHARON, Olivier HUDRY & Antoine LOBSTEIN
Centre National de la Recherche Scientifique
Ecole Nationale Supérieure des Télécommunications
46 rue Barrault, 75634 Paris cédex 13, France
{charon, hudry, lobstein}@infres.enst.fr
Abstract. Consider a connected undirected graph G=(V,E), a subset C of vertices, and an integer r greater than or equal to 1; for any vertex v in V, let Br(v) denote the ball of radius r centered at v, i.e., the set of all vertices linked to v by a path of at most r edges. If for all vertices v in V, the sets Br(v) $\cap$ C are all nonempty and different, then we call C an r-identifying code. A graph is said to be r-identifiable if it admits at least one r-identifying code. We prove the following structural properties of r-identifiable graphs. For any r greater than or equal to 1, any r-identifiable graph must have at least 2r+1 vertices. For r=1 and for any r-identifiable graph G with at least 2r+2 vertices, or for any r greater than or equal to 1 and for any r-identifiable tree G with at least 2r+2 vertices, there always exists at least one vertex such that its removing from G leaves an r-identifiable graph. This property is not true for r greater than or equal to 3 in general. The case r=2 remains open for general graphs.