Onα-labellings of lobsters and trees with a perfect matching
| Autor: | Atílio G. Luiz, C. N. Campos, R. Bruce Richter |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Combinatorics
Conjecture 010201 computation theory & mathematics Applied Mathematics 0211 other engineering and technologies Discrete Mathematics and Combinatorics 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology 01 natural sciences Injective function Mathematics |
| Zdroj: | Discrete Applied Mathematics. 268:137-151 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2019.05.004 |
| Popis: | A graceful labelling of a tree T is an injective function f : V ( T ) → { 0 , … , | E ( T ) | } such that { | f ( u ) − f ( v ) | : u v ∈ E ( T ) } = { 1 , … , | E ( T ) | } . An α -labelling of a tree T is a graceful labelling f with the additional property that there exists an integer k ∈ { 0 , … , | E ( T ) | } such that, for each edge u v ∈ 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 α -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 α -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 α -labelling. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect