Research Experiences for Undergraduates

Program in Mathematics at Mississippi State University

#####

#####

##### Summer 2003

** **

** **

### Colloquium

** **

#### Date: July 28, 2003

## Time:
4:00 PM

Location: Allen 411

**Speaker:
Dr. Ted Dobson, Mississippi State University**

**Title:**

Hamiltonian Cycles in Graphs

**Abstract:**

** **

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.