| Full text | |
| Author(s): |
Botler, Fabio
;
Jimenez, Andrea
Total Authors: 2
|
| Document type: | Journal article |
| Source: | DISCRETE MATHEMATICS; v. 340, n. 6, p. 1405-1411, JUN 2017. |
| Web of Science Citations: | 5 |
| Abstract | |
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) | |
| FAPESP's process: | 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science |
| Grantee: | Carlos Eduardo Ferreira |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 11/08033-0 - Decomposition of a graph into paths: structural and algorithmic aspects |
| Grantee: | Fábio Happ Botler |
| Support Opportunities: | Scholarships in Brazil - Doctorate |
| FAPESP's process: | 14/01460-8 - Graph decompositions |
| Grantee: | Fábio Happ Botler |
| Support Opportunities: | Scholarships abroad - Research Internship - Doctorate |