Improved bounds for relaxed graceful trees
No Thumbnail Available
Authors
Elliot Krop
Christian Barrientos
Issue Date
Type
Journal Article, Academic Journal
Language
Keywords
Alternative Title
Abstract
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 \cite{VB}. 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+3}{8}\}$ of the edge weights distinct, which is an improvement on a bound given by Rosa and \v{S}ir\'{a}\v{n} \cite{RS} on the $\alpha$-size of trees, for $d<\frac{m+22}{7}$ and $d>\frac{5m+19}{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 gracesize bound from \cite{RS} for certain values of $\nu$ and $d$. We view these results as a step towards Bermond's conjecture \cite{Bermond}.