A graph G is Hamiltonian if it has a spanning cycle. The problem of determining if a graph is Hamiltonian is well known to be NP-complete. While there are several necessary conditions for Hamiltonicity, the search continues for sufficient conditions. In their paper, "On Smallest Non-Hamiltonian Regular Tough Graphs" (Congressus Numerantium 70), Bauer, Broersma, and Veldman stated, without a formal proof, that all 4-regular, 2-connected, 1-tough graphs on fewer than 18 nodes are Hamiltonian. They also demonstrated that this result is best possible. Following a brief survey of some sufficient conditions for Hamiltonicity, Bauer, Broersma, and Veldman's result is demonstrated to be true for graphs on fewer than 16 nodes. Possible approaches for the proof of the n=16 and n=17 cases also will be discussed.
"A Study of Sufficient Conditions for Hamiltonian Cycles,"
Rose-Hulman Undergraduate Mathematics Journal: Vol. 1
, Article 6.
Available at: http://scholar.rose-hulman.edu/rhumj/vol1/iss1/6