Identifying And Locating-dominating Codes On Paths And Cycles

For a graph G and a set D (?) V(G), define N_r[x] = {x_i∈V(G) :d(x,x_i)≤r)(where d(x,y) is graph theoretic distance) and D_r(x) = N_r[x]∩D.D is known as an r - identifying code (r-locating-dominating code, respectively), if for all vertices x∈V(G)(x∈V(G)\D,respectively),D_r(x) are all nonempty and different. The various applications of these codes include attack sensor placement in networks and fault detection/localization in multiprocessor or distributed systems. Gravier et al.[Identifying codes of cycles, European Journal of Combinatorics 27 (2006) 767-776] provide partial results about the minimum size of D for r-identifying codes for paths and cycles and present complete closed form solutions for the case r=1,and Roberts et al. [Locating sensors in paths and cycles: The case of 2-identifying codes, European Journal of Combinatorics 29(2008) 72-82] provide complete results for the cycles and paths when r = 2. We provide complete results for r - identifying codes in cycles and paths, we also give complete results for 2 - locating - dominating codes in cycles.