Geodesic
Uniquely Hamiltonian characterizations of distance-hereditary and parity 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

A graph is shown to be distance-hereditary if and only if no induced subgraph of order five or more has a unique hamiltonian cycle; this is also equivalent to every induced subgraph of order five or more having an even number of hamiltonian cycles. Restricting the induced subgraphs to those of odd order five or more gives two similar characterizations of parity graphs. The close relationship between distance-hereditary and parity graphs is unsurprising, but their connection with hamiltonian cycles of induced subgraphs is unexpected.
DOI : 10.37236/911
Classification : 05C75, 05C45
Mots-clés : distance hereditary graphs, parity graphs, hamiltonian cycle, induced subgraph 
@article{10_37236_911,
     author = {Terry A. McKee},
     title = {Uniquely {Hamiltonian} characterizations of distance-hereditary and parity graphs},
     journal = {The electronic journal of combinatorics},
     year = {2008},
     volume = {15},
     doi = {10.37236/911},
     zbl = {1158.05333},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/911/}
}
TY  - JOUR
AU  - Terry A. McKee
TI  - Uniquely Hamiltonian characterizations of distance-hereditary and parity graphs
JO  - The electronic journal of combinatorics
PY  - 2008
VL  - 15
UR  - http://geodesic.mathdoc.fr/articles/10.37236/911/
DO  - 10.37236/911
ID  - 10_37236_911
ER  - 
%0 Journal Article
%A Terry A. McKee
%T Uniquely Hamiltonian characterizations of distance-hereditary and parity graphs
%J The electronic journal of combinatorics
%D 2008
%V 15
%U http://geodesic.mathdoc.fr/articles/10.37236/911/
%R 10.37236/911
%F 10_37236_911
Terry A. McKee. Uniquely Hamiltonian characterizations of distance-hereditary and parity graphs. The electronic journal of combinatorics, Tome 15 (2008). doi: 10.37236/911

Cité par Sources :