Research Experiences for Undergraduates

Program in Mathematics at Mississippi State University

Summer 2003





Date:  July 28, 2003

Time:  4:00 PM

Location:  Allen 411




Speaker:  Dr. Ted Dobson, Mississippi State University




Hamiltonian Cycles in Graphs




Graph theory is an area of mathematics that has become more important in recent time because graphs are natural models for, among other things, communication networks. Graph theory is well known in mathematics as being an area that has some problems that are quite easy to state, but are extremely difficult to solve. In this talk, we will give some basic definitions, and then state one such problem. Namely, we will discuss finding Hamiltonian cycles in connected graphs. We will also illustrate the difficulty of this problem by also discussing computational complexity. For those of greedy nature, two questions will be posed, the solutions of which will result in prizes. One solution will be worth a candy bar, the other $1,000,000 (and a candy bar). No prize will be given for figuring out which prize I will supply.



Refreshments served in our faculty lounge at 3:30 p.m.