Extremal cardinalities for identifying and locating-dominating codes in graphs

Consider a connected undirected graph G = (V, E), a subset of vertices C ⊆ V, and an integer r ≥ 1; for any vertex v ∈ V, let B_r (v) denote the ball of radius r centred 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 ∈ V (respectively, v ∈ V {minus 45 degree rule} C), the sets B_r (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 ⌈ log₂ (n + 1) ⌉ vertices; we establish in particular that such a code contains at mostn - 1 vertices, and we prove that these two bounds are reached. The same type of results are given for locating-dominating codes.