Extremal cardinalities for identifying and locating-dominating codes in graphs

Consider a connected undirected graph G = (V, E), a subset of vertices C subset of V, and an integer r >= 1; for any vertex nu is an element of V, let B-r(v) denote the ball of radius r centred at nu, i.e., the set of all vertices linked to nu by a path of at most r edges. If for all vertices nu is an element of V (respectively, nu is an element of V\C), the sets B-r(nu) boolean AND 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 [log(2)(n + 1)] 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. (c) 2006 Elsevier B.V. All rights reserved.