On alpha-labellings of lobsters and trees with a perfect matching

Autor(es)

Luiz, Atilio G. ^[1] ; Campos, C. N. ^[1] ; Richter, R. Bruce ^[2]

Afiliação do(s) autor(es)

^[1] Univ Estadual Campinas, Inst Comp, Sao Paulo - Brazil

^[2] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON - Canada

• Tipo de documento: Artigo Científico
• Fonte: DISCRETE APPLIED MATHEMATICS; v. 268, p. 137-151, SEP 15 2019.
• Citações Web of Science: 0

Resumo

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)

• Processo FAPESP: 14/16987-1 - Problemas estruturais em teoria de grafos
• Beneficiário: Christiane Neme Campos
• Modalidade de apoio: Bolsas no Exterior - Pesquisa
• Processo FAPESP: 15/03372-1 - Problemas de rotulação em grafos
• Beneficiário: Atilio Gomes Luiz
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Doutorado
• Processo FAPESP: 14/16861-8 - Problemas de rotulação em grafos
• Beneficiário: Atilio Gomes Luiz
• Modalidade de apoio: Bolsas no Brasil - Doutorado