Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

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

Texto completo
Autor(es):
Luiz, Atilio G. [1] ; Campos, C. N. [1] ; Richter, R. Bruce [2]
Número total de Autores: 3
Afiliação do(s) autor(es):
[1] Univ Estadual Campinas, Inst Comp, Sao Paulo - Brazil
[2] Univ Waterloo, Dept Combinator & Optimizat, Waterloo, ON - Canada
Número total de Afiliações: 2
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