Extremal cardinalities for identifying and locating-dominating codes in graphs (Q864121)

Given a graph \(G\), a vertex \(v \in V(G)\), and a positive integer \(r\), we define \(B_r(v) := \{ w \in V(G) : d(v,w) \leq r\}\). A code \(C \subseteq V(G)\) is said to be \(r\)-identifying (resp.\ \(r\)-locating-dominating) if for all vertices \(v \in V(G)\) (resp.\ \(v \in V(G)\setminus C\)), the sets \(B_r(v) \cap C\) are all nonempty and different. A minimum \(r\)-identifying code has size at least \(\lceil \log_2(n+1)\rceil\) (trivial) and at most \(n-1\), where \(n = |V(G)|\). It is here shown that there are indeed graphs whose minimum \(r\)-identifying codes have these sizes. A similar result is obtained for \(r\)-locating-dominating codes.