We introduce left and right-layered trees as trees with a specific representation and define the excess of a tree. Applying these ideas, we show a range-relaxed graceful labeling which improves on the upper bound for maximum vertex label given by Van Bussel. For the case when the tree is a lobster of size m and diameter d, the labeling produces vertex labels no greater than \(\frac{3}{2}m-\frac{1}{2}d\). Furthermore, we show that any lobster T with m edges and diameter d has an edge-relaxed graceful bipartite labeling with at least \(\max \{\frac{3m-d+6}{4},\frac{5m+d+15}{8}\}\) of the edge weights distinct, which is an improvement on a bound given by Rosa and Siraň on the \(\alpha \)-size of trees, for \(d \frac{5m-65}{7}\). We also show that there exists an edge-relaxed graceful labeling (not necessarily bipartite) with at least \(\max \left\{ \frac{3}{4}m+\frac{d-\nu }{8}+\frac{3}{2},\nu \right\} \) of the edge weights distinct, where \(\nu \) is twice the size of a partial matching of T. This is an improvement on the best known gracesize bound, for certain values of \(\nu \) and d. We view these results as a step towards Bermond’s conjecture that all lobsters are graceful.
['Christian Barrientos', 'Elliot Krop']
Improved Bounds for Relaxed Graceful Trees