Extremal cardinalities for identifying and locating-dominating codes in graphs

Consider a connected undirected graph G=(V,E)G=(V,E), a subset of vertices C⊆VC⊆V, and an integer r⩾1r⩾1; for any vertex v∈Vv∈V, let Br(v)Br(v) denote the ball of radius r   centred at vv, i.e., the set of all vertices linked to vv by a path of at most r   edges. If for all vertices v∈Vv∈V (respectively, v∈V⧹Cv∈V⧹C), the sets Br(v)∩CBr(v)∩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 ⌈log2(n+1)⌉⌈log2(n+1)⌉ vertices; we establish in particular that such a code contains at most  n-1n-1 vertices, and we prove that these two bounds are reached. The same type of results are given for locating-dominating codes.