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

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.


If you have specific questions about this project, please contact Dr. Nicolas directly at Cnicolas@ferrum.edu.

                                                                 FSP Apply button

     Click here to return to the Freshman Scholars Program Overview page.