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.)

Decomposing 8-regular graphs into paths of length 4

Texto completo
Autor(es):
Botler, F. ; Talon, A.
Número total de Autores: 2
Tipo de documento: Artigo Científico
Fonte: DISCRETE MATHEMATICS; v. 340, n. 9, p. 2275-2285, SEP 2017.
Citações Web of Science: 1
Resumo

A T-decomposition of a graph G is a set of edge-disjoint copies of T in G that cover the edge set of G. Graham and Haggkvist (1989) conjectured that any 2l-regular graph G admits a T-decomposition if T is a tree with l edges. Kouider and Lonc (1999) conjectured that, in the special case where T is the path with l edges, G admits a T-decomposition D where every vertex of G is the end-vertex of exactly two paths of D, and proved that this statement holds when G has girth at least (l + 3)/2. In this paper we verify Kouider and Lonc's Conjecture for paths of length 4. (C) 2017 Elsevier B.V. All rights reserved. (AU)

Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
Beneficiário:Carlos Eduardo Ferreira
Linha de fomento: Auxílio à Pesquisa - Temático
Processo FAPESP: 11/08033-0 - Decomposição de um grafo em caminhos: aspectos estruturais e algorítmicos
Beneficiário:Fábio Happ Botler
Linha de fomento: Bolsas no Brasil - Doutorado
Processo FAPESP: 14/01460-8 - Decomposições de grafos
Beneficiário:Fábio Happ Botler
Linha de fomento: Bolsas no Exterior - Estágio de Pesquisa - Doutorado