DIMACS TR: 2003-25

On a problem of Lesniak, Polimeni, and Vanderjagt

Author: Igor Zverovich


We give almost complete solution to the following problem: for a fixed S, what is the minimum value p = uH (S) such that a pair (S; p) has a Hamiltonian realization?

We give a criterion for a pair (S; p) to have a Hamiltonian realization.

AMS Subject Classi cation: 05C35.

Keywords: Degree set, Hamiltonian graph.

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

DIMACS Home Page