Labellings of trees with maximum degree three - an improved bound

Brankovic, L.; Rosa, A. and Siran, J. (2005). Labellings of trees with maximum degree three - an improved bound. Journal of Combinatorial Mathematics and Combinatorial Computing, 55 pp. 159–169.

URL: http://www.zentralblatt-math.org/zmath/search/?an=...

Abstract

If $T=(V,E)$ is a tree on vertex set $V$ , where $|V|=n$ , a labelling of $T$ is a bijection $\phi$ from $V$ to $\{1,2,\dots,n\}$ . The labelling induces an edge labelling ${\overline \phi}: E\rightarrow \{1,2,\dots,n-1\}$ by ${\overline \phi}(e)=|\phi(u)-\phi(v)|$ for $e=uv\in E$ . The size of the labelling $\phi$ is $|{\overline \phi}(E)|$ . A labelling is graceful if its size is $n-1$ . The famous graceful tree conjecture states that every tree has a graceful labelling. This conjecture is open even for trees with maximum degree 3. A labelling of $T$ is bipartite, if there is real number that separates the labels of the natural 2-coloration of $T$ , i.e. labels from one class are below, labels from the other class are above the number. The gracesize gs $(T)$ is the maximum size of a labelling of $T$ , and the $\alpha$ -size $\alpha(T)$ is the maximum size of a bipartite labelling of $T$ . It is not true that $\alpha(T)$ were always $n-1$ . However the paper shows that for trees with maximum degree 3 we have $\alpha(T)\geq \lfloor 7n/8\rfloor -1$ . Perhaps it is $\geq n-c$ for some constant $c$ .