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$.

Viewing alternatives

Item Actions

Export

About

Recommendations