0-Centred and 0-ubiquitously graceful trees Original Research Article

A tree T is k-centred graceful if it has a graceful labelling f such that f assigns the label k to the centre vertex (or one of the centres if the tree has odd diameter); similarly, a graph G is k-ubiquitously graceful if for every vertex v∈V(G) there is a graceful labelling f of G such that f(v)=k. In this paper we isolate a small and easily characterized subset of trees that are not 0-centred graceful, and a larger but still very manageable set of non-0-ubiquitously graceful trees; these we denote by D and D′, respectively. It is shown that all trees of diameter ⩽4 that are not in D are 0-centred graceful, and all that are not in D′ are 0-ubiquitously graceful. Upon consideration of some very intriguing empirical data we conjecture that these results in fact extend to all trees.