Common Techniques in Graceful Tree Labeling with a New Computational Approach

The graceful tree conjecture was first introduced over 50 years ago, and to this day it remains largely unresolved. Ideas for how to label arbitrary trees have been sparse, and so most work in this area focuses on demonstrating that particular classes of trees are graceful. In my research, I continue this effort and establish the gracefulness of some new tree types using previously developed techniques for constructing graceful trees. Meanwhile, little work has been done on developing computational methods for obtaining graceful labelings, as direct approaches are computationally infeasible for even moderately large trees. With this in mind, I have designed a new computational approach for constructing a graceful labeling for trees with sufficiently many leaves. This approach leverages information about the local structures present in a given tree in order to construct a suitable labeling. It has been shown to work for many small cases and thoughts on how to extend this approach for larger trees are put forth.

Name thesis:degree_name

MS

Level thesis:degree_level

Immediate Access

Discipline thesis:degree_discipline

Computational Mathematics

Year dc:date.available

2016

Author dc:creator

• Guyer, Michael

Contributors dc:contributor

• Karl Wimmer
• Rachael Neilan
• John Kern

• Computational
• Expansion
• Graceful Labeling
• Graph Theory
• Tree

Language dc:language

English

Repository record dc:identifier

https://dsc.duq.edu/etd/609

OAI identifier oai:identifier

oai:dsc.duq.edu:etd-1625