کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419896 | 683872 | 2011 | 8 صفحه PDF | دانلود رایگان |

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.
Journal: Discrete Applied Mathematics - Volume 159, Issue 15, 6 September 2011, Pages 1540–1547