Extremal cardinalities for identifying and locating-dominating codes in graphs Original Research Article

Consider a connected undirected graph image, a subset of vertices image, and an integer image; for any vertex image, let image denote the ball of radius r centred at image, i.e., the set of all vertices linked to image by a path of at most r edges. If for all vertices image (respectively, image), the sets image 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 image vertices; we establish in particular that such a code contains at most image vertices, and we prove that these two bounds are reached. The same type of results are given for locating-dominating codes.