# 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=... Look up in Google Scholar

## Abstract

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 0835-3026 Mathematics, Computing and Technology > Mathematics and StatisticsMathematics, Computing and Technology 8077 Jozef Širáň 15 Jun 2007 14 Jan 2016 16:32 http://oro.open.ac.uk/id/eprint/8077

### Actions (login may be required)

 RDF+XMLBibTeXRIOXX2 XMLRDF+N-TriplesJSONDublin CoreAtomOAI-ORE Resource Map (Atom Format)Simple MetadataReferMETSOAI-ORE Resource Map (RDF Format)HTML CitationASCII CitationMultiline CSVRefMan RIS Format (UTF-8)OpenURL ContextObjectEndNoteMODSOpenURL ContextObject in SpanMPEG-21 DIDLEP3 XMLRefMan RIS FormatRDF+N3Eprints Application Profile
© The Open University   + 44 (0)870 333 4340   general-enquiries@open.ac.uk