Identifying codes and locating–dominating sets on paths and cycles

Let G=(V,E)G=(V,E) be a graph and let r≥1r≥1 be an integer. For a set D⊆VD⊆V, define Nr[x]={y∈V:d(x,y)≤r}Nr[x]={y∈V:d(x,y)≤r} and Dr(x)=Nr[x]∩DDr(x)=Nr[x]∩D, where d(x,y)d(x,y) denotes the number of edges in any shortest path between xx and yy. DD is known as an rr-identifying code (rr-locating-dominating set, respectively), if for all vertices x∈Vx∈V (x∈V∖Dx∈V∖D, respectively), Dr(x)Dr(x) are all nonempty and different. Roberts and Roberts [D.L. Roberts, F.S. Roberts, Locating sensors in paths and cycles: the case of 2-identifying codes, European Journal of Combinatorics 29 (2008) 72–82] provided complete results for the paths and cycles when r=2r=2. In this paper, we provide results for a remaining open case in cycles and complete results in paths for rr-identifying codes; we also give complete results for 2-locating-dominating sets in cycles, which completes the results of Bertrand et al. [N. Bertrand, I. Charon, O. Hudry, A. Lobstein, Identifying and locating–dominating codes on chains and cycles, European Journal of Combinatorics 25 (2004) 969–987].

► We provide results for a remaining open case in cycles for rr-identifying codes. ► We provide complete results in paths for rr-identifying codes. ► We give complete results for 2-locating-dominating sets in cycles.