The Graceful Tree Algorithm Fiona Bogart Faculty mentor: Eirini Poimenidou New College of Florida
A well-known open problem in graph theory is the Graceful Tree Conjecture, which states that any tree with n vertices may be labeled gracefully. In other words, each vertex of the tree may be labeled with the integers 1 through n so that the absolute difference of the labels of each edge’s endpoints is distinct. We develop an algorithm capable of constructing a tree with n vertices and a graceful labeling. The algorithm works backwards by labeling the vertices of Kn by the integers 1 through n and then the edges by the absolute difference of their endpoints' labels. The algorithm then proceeds to have us choose and delete appropriate edges from the labeled complete graph until we obtain a gracefully labeled tree. We then explore the class of trees the algorithm is capable of producing, which we call algorithmic trees. We demonstrate that stars, paths, and caterpillars are algorithmic.
Fiona Bogart is a third-year mathematics student at New College of Florida. They enjoy thinking about and visualizing abstract mathematics, and their primary interests lie in graph theory, abstract algebra, and Riemann surfaces.
