Induced paths in twin-free graphs (Q1010672)

Summary: 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 sugbraph, i.e. a chordless path.