Brankovic, L.; Rosa, A. and Siran, J.
|Google Scholar:||Look up in Google Scholar|
If is a tree on vertex set , where , a labelling of is a bijection from to . The labelling induces an edge labelling by for . The size of the labelling is . A labelling is graceful if its size is . 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 is bipartite, if there is real number that separates the labels of the natural 2-coloration of , i.e. labels from one class are below, labels from the other class are above the number. The gracesize gs is the maximum size of a labelling of , and the -size is the maximum size of a bipartite labelling of . It is not true that were always . However the paper shows that for trees with maximum degree 3 we have . Perhaps it is for some constant .
|Item Type:||Journal Article|
|Academic Unit/Department:||Mathematics, Computing and Technology > Mathematics and Statistics|
|Depositing User:||Jozef Širáň|
|Date Deposited:||15 Jun 2007|
|Last Modified:||02 Dec 2010 20:00|
|Share this page:|