\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf David Auger}
%
%
\medskip
\noindent
%
%
{\bf Induced Paths in Twin-Free Graphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
Let $G=(V,E)$ be a simple, undirected graph. Given an integer $r \geq
1$, we say that $G$ is {$r$-\it twin-free} (or $r$-{\it identifiable})
if the balls $B(v,r)$ for $v \in V$ are all different, where $B(v,r)$
denotes the set of all vertices which can be linked to $v$ by a path
with at most $r$ edges. These graphs are precisely the ones which
admit $r$-identifying codes. We show that if a graph $G$ is
$r$-twin-free, then it contains a path on $2r+1$ vertices as an
induced sugbraph, i.e. a chordless path.



\bye

.