| Full text | |
| Author(s): |
Total Authors: 3
|
| Affiliation: | [1] Univ Estadual Campinas, Inst Comp, Sao Paulo - Brazil
[2] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON - Canada
Total Affiliations: 2
|
| Document type: | Journal article |
| Source: | DISCRETE APPLIED MATHEMATICS; v. 268, p. 137-151, SEP 15 2019. |
| Web of Science Citations: | 0 |
| Abstract | |
A graceful labelling of a tree T is an injective function f: V(T) -> [0, ..., vertical bar E(T)vertical bar] such that [vertical bar f(u) - f (v)vertical bar: uv is an element of E(T)] = [1, ..., vertical bar E(T)vertical bar]. An alpha-labelling of a tree T is a graceful labelling f with the additional property that there exists an integer k is an element of [0, ..., vertical bar E(T)vertical bar] such that, for each edge uv is an element of E(T), either f(u) <= k < f(v) or f(v) <= k < f(u). In this work, we prove that the following families of trees with maximum degree three have alpha-labellings: lobsters with maximum degree three, without Y-legs and with at most one forbidden ending; trees T with a perfect matching M such that the contraction T/M has a balanced bipartition and an alpha-labelling; and trees with a perfect matching such that their contree is a caterpillar with a balanced bipartition. These results are a step towards the conjecture posed by Bermond in 1979 that all lobsters have graceful labellings and also reinforce a conjecture posed by Brankovic, Murch, Pond and Rosa in 2005, which says that every tree with maximum degree three and a perfect matching has an alpha-labelling. (C) 2019 Elsevier B.V. All rights reserved. (AU) | |
| FAPESP's process: | 14/16987-1 - Selected structural problems in graph theory |
| Grantee: | Christiane Neme Campos |
| Support Opportunities: | Scholarships abroad - Research |
| FAPESP's process: | 15/03372-1 - Some labelling problems on graphs |
| Grantee: | Atilio Gomes Luiz |
| Support Opportunities: | Scholarships abroad - Research Internship - Doctorate |
| FAPESP's process: | 14/16861-8 - Problems on graph labelling |
| Grantee: | Atilio Gomes Luiz |
| Support Opportunities: | Scholarships in Brazil - Doctorate |