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\).


05C78 Graph labelling (graceful graphs, bandwidth, etc.)
05C05 Trees