Locating sensors in paths and cycles: The case of 2-identifying codes

AbstractFor a graph G and a set D⊆V(G), define Nr[x]={xi∈V(G):d(x,xi)≤r} (where d(x,y) is graph theoretic distance) and Dr(x)=Nr[x]∩D. D is known as an r-identifying code if for every vertex x,Dr(x)≠0̸, and for every pair of vertices x and y, x≠y⇒Dr(x)≠Dr(y). The various applications of these codes include attack sensor placement in networks and fault detection/localization in multiprocessor or distributed systems. 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] and Gravier et al. [S. Gravier, J. Moncel, A. Semri, 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, based in part on Daniel [M. Daniel, Codes identifiants, Rapport pour le DEA ROCO, Grenoble, June 2003]. We provide complete solutions for the case r=2