Geodesic
Induced paths in twin-free graphs
The electronic journal of combinatorics, Tome 15 (2008)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/892
Classification : 05C12, 05C35, 05C38
Mots-clés : r-twin-free graphs, r-identifiable, balls, chordless path 
@article{10_37236_892,
     author = {David Auger},
     title = {Induced paths in twin-free graphs},
     journal = {The electronic journal of combinatorics},
     year = {2008},
     volume = {15},
     doi = {10.37236/892},
     zbl = {1160.05316},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/892/}
}
TY  - JOUR
AU  - David Auger
TI  - Induced paths in twin-free graphs
JO  - The electronic journal of combinatorics
PY  - 2008
VL  - 15
UR  - http://geodesic.mathdoc.fr/articles/10.37236/892/
DO  - 10.37236/892
ID  - 10_37236_892
ER  - 
%0 Journal Article
%A David Auger
%T Induced paths in twin-free graphs
%J The electronic journal of combinatorics
%D 2008
%V 15
%U http://geodesic.mathdoc.fr/articles/10.37236/892/
%R 10.37236/892
%F 10_37236_892
David Auger. Induced paths in twin-free graphs. The electronic journal of combinatorics, Tome 15 (2008). doi: 10.37236/892

Cité par Sources :