On -locating–dominating sets in paths

Assume that G = ( V , E ) is a simple undirected graph, and C is a nonempty subset of V . For every v ∈ V , we define I r ( v ) = { u ∈ C ∣ d G ( u , v ) ≤ r } , where d G ( u , v ) denotes the number of edges on any shortest path between u and v . If the sets I r ( 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.