Decomposing highly connected graphs into paths of length five

Autor(es)

Botler, F. ; Mota, G. O. ; Oshiro, M. T. I. ; Wakabayashi, Y.

• Tipo de documento: Artigo Científico
• Fonte: DISCRETE APPLIED MATHEMATICS; v. 245, p. 11-pg., 2018-08-20.

Resumo

Bark and Thomassen (2006) posed the following decomposition conjecture: for each tree T, there exists a natural number k(T) such that, if G is a k(T)-edge-connected graph and vertical bar E(G)vertical bar is divisible by vertical bar E(T)vertical bar, then G admits a decomposition into copies of T. In a series of papers, Thomassen verified this conjecture for stars, some bistars, paths of length 3, and paths whose length is a power of 2. We verify this conjecture for paths of length 5. (C) 2016 Elsevier B.V. All rights reserved. (AU)

• Processo FAPESP: 11/08033-0 - Decomposição de um grafo em caminhos: aspectos estruturais e algorítmicos
• Beneficiário: Fábio Happ Botler
• Modalidade de apoio: Bolsas no Brasil - Doutorado
• Processo FAPESP: 13/11431-2 - Combinatória extremal e probabilística
• Beneficiário: Guilherme Oliveira Mota
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado
• Processo FAPESP: 13/20733-2 - Combinatória extremal e probabilística
• Beneficiário: Guilherme Oliveira Mota
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Pós-Doutorado
• Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
• Beneficiário: Carlos Eduardo Ferreira
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 14/01460-8 - Decomposições de grafos
• Beneficiário: Fábio Happ Botler
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Doutorado