Induced Paths in Twin-Free Graphs

Source abstract

Let $G=(V,E)$ be a simple, undirected graph. Given an integer $r \geq 1$, we say that $G$ is $r$-twin-free (or $r$-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 subgraph, i.e. a chordless path.