Presentation Type
Poster Presentation
Symposium Date
Spring 2012
Abstract
The Graceful Tree Conjecture in graph theory has been open for almost half a century. The conjecture states that the vertices of any tree can be labeled with distinct integers between 0 and the number of edges of the tree in a way that the edges can be uniquely identified by the absolute value of the difference between their vertex labels. One possible approach to prove the conjecture is to prove the more general k-equitable tree conjecture. In a k-equitable labeling we assign integers from the set {0,1,2,…,k-1} to the vertices. Each edge will receive a label that is the absolute value of the difference of its vertex labels. We want to distribute the labels as equally as possible both for the edges and for the vertices. The conjecture states that this kind of labeling is possible for every tree and every k. This conjecture is equivalent to the graceful tree conjecture when k is the number of vertices of the tree. It has already been proven that every tree is 2-equitable and 3-equitable. We attempt to show a part of the k-equitable tree conjecture by choosing a large collection of trees called caterpillars, and examining different values of k.
Recommended Citation
Burek, Mark; Olson, William; and Taulbee, Brock, "Equitable Labelings of Caterpillar Graphs" (2012). Symposium on Undergraduate Research and Creative Expression (SOURCE). 132.
https://scholar.valpo.edu/cus/132
Biographical Information about Author(s)
Link is to abstract only.