## DIMACS TR: 2004-22

##
A Degree Constraint for Uniquely Hamiltonian Graphs

### Authors: Sarmad Abbasi and Asif Jamshed

**
ABSTRACT
**
A graph, $G,$ is called uniquely Hamiltonian if it contains exactly one
Hamilton cycle. We show that if $G=(V,E)$ is uniquely Hamiltonian then
$$ \sum_{v \in V} \left( 2 \over 3 \right) ^{d(v)-\#(G)} \geq 1.$$
Where $\#(G) = 1$ if $G$ has even number of vertices and $2$ if $G$ has
odd number of vertices. It follows that every $n$-vertex uniquely
Hamiltonian graph contains a vertex whose degree is at most $c \log_2 n +
2$ where $c=\left(\log_2 3 -1 \right)^{-1} \approx 1.71$ thereby
improving a bound given by Bondy and Jackson.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2004/2004-22.ps.gz

DIMACS Home Page