The Graceful Labeling Conjecture: A Programming Approach
Instructor: Carlos Nicolas, Ph.D.
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.
If you have specific questions about this project, please contact Dr. Nicolas directly