\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Terry A. McKee}
%
%
\medskip
\noindent
%
%
{\bf Uniquely \ Hamiltonian \ Characterizations \ of \ Distance-Hereditary and Parity Graphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
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.
\bye