2014/03/06 by Matthew C. Superdock, Superdock, Matthew C.
Computer Science · Mathematics · #05C78 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #math.CO #msc:05C78
paper · pdf · doi:10.48550/arxiv.1403.1564
Undergraduate thesis, Princeton University, May 2013; this is valuable mainly for the survey in section 2 and the results in sections 4.4-5.3--the lemmas and main results in sections 3.1-4.3 are more clearly presented in my more recent paper (arXiv:1402.6570)
arxiv created 2014/03/06 · openalex publication_date 2014/03/06 · arxiv updated 2014/03/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We survey the current state of progress on the Graceful Tree Conjecture, and then we present several new results toward the conjecture, driven by three new ideas: (1) It has been proven that generalized banana trees are graceful by rearranging the branches at the root--consider rearranging branches at all internal vertices; (2) The method of transfers has typically involved type-1 transfers and type-2 transfers--all type-2 transfers are type-1 transfers in disguise, and hence can be removed from the discussion; (3) The method of transfers has typically used the sequence of transfers 0→ n→ 1→ n - 1→⋯--transfer backwards to manipulate the resulting labels. Using these ideas, we prove that several classes of diameter-6 trees are graceful, and we generalize some of these classes to larger trees. We also introduce a class of graceful spiders, prove that attaching sufficiently many leaves to any tree gives a graceful tree, and extend known results on trees with perfect matchings.