# Freshman Scholars Program 2014

# The Graceful Labeling Conjecture: A Programming Approach

### Instructor: Carlos Nicolas, Ph.D.

#### Project Description:

*Students interested in mathematics, computer science, or computer information systems.*

Graphs are simple mathematical objects consisting of a set of *vertices* and a set of *edges* joining the vertices. For example, a road map of the USA is a graph in which the
cities are the vertices and the roads joining the cities are the edges. The eight
corners and twelve edges of a cube also form a graph. The study of graphs at the introductory
level requires no technical knowledge beyond high-school algebra.

There are numerous questions about graphs that still remain open. One of them is the famous graceful labeling conjecture for trees (a tree is a type of graph). In this project, the student(s) - assisted by the instructor - will use a Computer Algebra System to verify this conjecture for particular cases, i.e., for trees with simple properties (e.g., having a small number of branches). The evidence gathered from the computer will be used to prove the conjecture for other trees with the same properties. By considering increasingly complex classes of trees, the student(s) will understand the difficulty involved in proving the general conjecture and why nobody has been able to prove it.

The project does not require previous programming experience or previous exposure to graph theory.

## Carlos Nicolas, Ph.D.## Dr. Nicolas obtained his Ph.D. in Mathematics from the University of Kentucky. He is particularly interested in combinatorics, graph theory, and combinatorial geometry. He has published several papers in the area of combinatorial geometry. He teaches a wide range of mathematics courses at Ferrum College, from MTH-100 to the senior seminar, including Graph Theory. |