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
ABSTRACT
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