On r-locating–dominating sets in paths

AbstractAssume that G=(V,E) is a simple undirected graph, and C is a nonempty subset of V. For every v∈V, we define Ir(v)={u∈C∣dG(u,v)≤r}, where dG(u,v) denotes the number of edges on any shortest path between u and v. If the sets Ir(v) for v∉C are pairwise different, and none of them is the empty set, we say that C is an r-locating–dominating set in G. It is shown that the smallest 2-locating–dominating set in a path with n vertices has cardinality ⌈(n+1)/3⌉, which coincides with the lower bound proved earlier by Bertrand, Charon, Hudry and Lobstein. Moreover, we give a general upper bound which improves a result of Bertrand, Charon, Hudry and Lobstein