| Full text | |
| Author(s): |
Botler, F.
;
Talon, A.
Total Authors: 2
|
| Document type: | Journal article |
| Source: | DISCRETE MATHEMATICS; v. 340, n. 9, p. 2275-2285, SEP 2017. |
| Web of Science Citations: | 1 |
| Abstract | |
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) | |
| 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 |