Induced paths in twin-free graphs (Q1010672)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Induced paths in twin-free graphs |
scientific article |
Statements
Induced paths in twin-free graphs (English)
0 references
7 April 2009
0 references
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.
0 references
r-twin-free graphs
0 references
r-identifiable
0 references
balls
0 references
chordless path
0 references