Towards the graceful tree conjecture

grantor: University of TorontoIn this thesis we present several results about graceful and near-graceful labellings of trees. Various modifications of the conditions for graceful and bipartite graceful labellings are probed; we conjecture that much stronger assumptions about graceful labellings than previously considered can be applied to all trees, and we provide evidence towards these conjectures. The most significant result of this thesis concerns a strengthening of the graceful labelling condition which requires that the centre vertex of a tree be assigned the label 0; labellings which satisfy this extra constraint are called '0-centred graceful'. Empirical results are presented which indicate that non-0-centred graceful trees constitute a very small and easily characterized subset of diameter 4 trees; it is shown that for all orders no member of this subset has a 0-centred graceful labelling, and that all other trees of diameter < 4 do have one. These results are extended to 0-labellings of arbitrary vertices via the notion of '0-ubiquitously graceful' trees; similar results (both empirical and theoretical) are obtained with respect to these. As well, some bounds are presented for certain relaxed graceful labellings of trees, empirical data concerning the prevalence of bipartite graceful trees is analyzed, and a weakened form of bipartite labelling called 'locally bipartite' is investigated.M.Sc