DIMACS TR: 2006-02

The Paradoxical Nature of Locating Sensors in Paths and Cycles:
The Case of 2-Identifying Codes

Authors: David L. Roberts and Fred S. Roberts


For a graph $G$ and a set $D \subseteq V(G)$, define $N_r[x] = \{x_i \in V(G): d(x,x_i) \leq r\}$ (where $d(x,y)$ is graph theoretic distance) and $D_r(x) = N_r[x] \cap D$. $D$ is known as an $r$-identifying-code if for every vertex $x, D_r(x) \neq \emptyset$, and for every pair of vertices $x$ and $y$, $x \neq y \Rightarrow D_r(x) \neq D_r(y)$. The various applications of these codes include attack sensor placement in networks and fault detection/localization in multiprocessor or distributed systems. In~\cite{BCHL04}~and~\cite{gravier}, partial results about the minimum size of $D$ for $r$-identifying codes are given for paths and cycles and complete closed form solutions are presented for the case $r = 1$, based in part on~\cite{Daniel}. We provide complete solutions for the case $r = 2$ as well as present our own solutions (verifying earlier results) to the $r = 1$ case. We use these closed form solutions to illustrate some surprisingly counterintuitive behavior that arises when the length of the path or cycle or the value of $r$ varies.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2006/2006-02.pdf
DIMACS Home Page