Extremal Cardinalities for Identifying and Locating-Dominating Codes in Graphs
Discrete Mathematics, Vol. 307, pp. 356-366, 2007.
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 (respectively, v in V\C), the sets Br(v) $\cap$ C are all nonempty and different, then we call C an r-identifying code (respectively, an r-locating-dominating code).
We study the extremal values of the cardinality of a minimum r-identifying or r-locating-dominating code in any connected undirected graph G having a given number, n, of vertices. It is known that a minimum r-identifying code contains at least $lceil$log2(n+1)$rceil$ vertices; we establish in particular that such a code contains at most n-1 vertices, and we prove that these two bounds are reached. The same type of results are given for locating-dominating codes.