Research Experiences for Undergraduates
Program in Mathematics at Mississippi State University
Location: Allen 411
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.