•  
  •  
 

Abstract

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.

Author Bio

Melissa DeLeon is a senior Mathematics/Secondary Education major atSeton HallUniversity who will be graduating in May 2000 with highest honors. Thispaper isthe culmination of a senior independent project completed under theguidance of Dr.John T. Saccoman. It was presented at the Second Annual Conference forUndergraduate Women in Mathematics at the University ofNebraska--Lincoln. Melissa has also been nominated for the Distinguished TeacherCandidate Award,a prestigious award from the New Jersey Department of Education. Sheplans toteach mathematics at the high school level in Northern New Jersey whereshe resideswith her husband, Shane. When not thinking mathematics or teaching,Melissa can befound in the theatre, where she has performed in and/or directed manyshowsincluding: A Christmas Carol, A Few Good Men, Oliver!, Dead Men Don'tNeed DressRehearsals, Guys and Dolls, Damn Yankees, and Alice in Wonderland.

Download

Share

COinS