| Texto completo | |
| Autor(es): |
Botler, Fabio
;
Jimenez, Andrea
Número total de Autores: 2
|
| Tipo de documento: | Artigo Científico |
| Fonte: | DISCRETE MATHEMATICS; v. 340, n. 6, p. 1405-1411, JUN 2017. |
| Citações Web of Science: | 5 |
| Resumo | |
Tibor Gallai conjectured that the edge set of every connected graph G on n vertices can be partitioned into {[}n/2] paths. Let G(k) be the class of all 2k-regular graphs of girth at least 2k-2 that admit a pair of disjoint perfect matchings. In this work, we show that Gallai's conjecture holds in G(k), for every k >= 3. Further, we prove that for every graph G in G(k) on n vertices, there exists a partition of its edge set into n/2 paths of lengths in [2k-1, 2k, 2k+1] and cycles of length 2k. (C) 2016 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 |
| Modalidade de apoio: | 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 |
| Modalidade de apoio: | Bolsas no Brasil - Doutorado |
| 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 |