# zbMATH — the first resource for mathematics

Labellings of trees with maximum degree three – an improved bound. (English) Zbl 1109.05095
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$$.

##### MSC:
 05C78 Graph labelling (graceful graphs, bandwidth, etc.) 05C05 Trees
##### Keywords:
graceful tree conjecture