Description:  Two radio stations that are close in distance must have frequencies that differ by a large amount to reduce interference.  We can represent this situation with a graph in which each vertex represents a radio station and an edge connects two vertices if the stations are close and may cause interference.  Students working on this project will try to determine the smallest span of numbers needed to prevent interference.

Research students will try to label the vertices of a graph subject to a list of conditions.  Once patterns emerge, the students will prove that they have found the best case.  For instance, we could label a graph with positive numbers so that vertices next to each other have labels that differ by at least three, vertices that are a distance of two apart have labels that differ by at least two, and vertices that are a distance of three apart have labels that differ by at least one.  Using these criteria, here is an example of two different ways to label the same graph:

The labeling on the right is a "better" labeling of this graph because its largest label is smaller than the largest label in the left graph.  Is there a way to label this graph so that the largest number is smaller than 11?

The students working on this project will look at a general case of the above labeling problem.  For particular groups of graphs we will find a labeling that minimizes the largest label and we will prove that there does not exist another labeling with a smaller maximum label.

For more information about this project contact Deb Czarneski, Carver 331A.