2004-22: A Degree Constraint for Uniquely Hamiltonian Graphs

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