Uniquely Hamiltonian Characterizations of Distance-Hereditary and Parity Graphs

Abstract

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.