The Open UniversitySkip to content

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.

Google Scholar: Look up in Google Scholar


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

Item Type: Journal Article
ISSN: 0835-3026
Academic Unit/Department: Mathematics, Computing and Technology > Mathematics and Statistics
Mathematics, Computing and Technology
Item ID: 8077
Depositing User: Jozef Širáň
Date Deposited: 15 Jun 2007
Last Modified: 14 Jan 2016 16:32
Share this page:

▼ Automated document suggestions from open access sources

Actions (login may be required)

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340