Uniquely Hamiltonian characterizations of distance-hereditary and parity graphs (Q1010695)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Uniquely Hamiltonian characterizations of distance-hereditary and parity graphs |
scientific article; zbMATH DE number 5540898
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Uniquely Hamiltonian characterizations of distance-hereditary and parity graphs |
scientific article; zbMATH DE number 5540898 |
Statements
Uniquely Hamiltonian characterizations of distance-hereditary and parity graphs (English)
0 references
7 April 2009
0 references
Summary: 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.
0 references
distance hereditary graphs
0 references
parity graphs
0 references
hamiltonian cycle
0 references
induced subgraph
0 references
