University Of Tasmania
GracefulTreesStatisticsAndAlgorithms.pdf (651.97 kB)
Download file

Graceful Trees: Statistics and Algorithms

Download (651.97 kB)
posted on 2023-05-26, 07:35 authored by Horton, M
The Graceful Tree Conjecture is a problem in graph theory that dates back to 1967. It suggests that every tree on n nodes can be labelled with the integers [1..n] such that the edges, when labelled with the difference between their endpoint node labels, are uniquely labelled with the integers [1..n-1]. To date, no proof or disproof of the conjecture has been found, but all trees with up to 28 vertices have been shown to be graceful. The conjecture also leads to a problem in algorithm design for efficiently finding graceful labellings for trees. In this thesis, a new graceful labelling algorithm is described and used to show that all trees on 29 vertices are graceful. A study is also made of statistical trends in the proportion of tree labellings that are graceful. These trends offer strong additional evidence that every tree is graceful.


Publication status

  • Unpublished

Repository Status

  • Open

Usage metrics

    Thesis collection


    No categories selected