Let G=(V,E) be a graph and let r<1 be an integer. For a set D?V, define ~(Nr)[x]=y∈V:d(x,y)≤r and ~(Dr)(x)= ~(Nr)[x]∩D, where d(x,y) denotes the number of edges in any shortest path between x and y. D is known as an r-identifying code (r-locating- dominating set, respectively), if for all vertices x∈V (x∈VD, respectively), ~(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) 7282] provided complete results for the paths and cycles when r=2. In this paper, we provide results for a remaining open case in cycles and complete results in paths for r-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 locatingdominating codes on chains and cycles, European Journal of Combinatorics 25 (2004) 969987].
展开▼
