Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777356 | European Journal of Combinatorics | 2017 | 9 Pages |
Abstract
A Pâ-decomposition of a graph G is a set of pairwise edge-disjoint paths with â edges that cover the edge set of G. In 1957, Kotzig proved that a 3-regular graph admits a P3-decomposition if and only if it contains a perfect matching, and also asked what are the necessary and sufficient conditions for an â-regular graph to admit a Pâ-decomposition, for odd â. Let g, â and m be positive integers with gâ¥3. We prove that, (i) if â is odd and m>2â(ââ2)â(gâ2)â, then every mâ-regular graph with girth at least g that contains an m-factor admits a Pâ-decomposition; (ii) if m>â(ââ2)â(gâ2)â, then every 2mâ-regular graph with girth at least g admits a Pâ-decomposition. Furthermore, we prove that, for graphs with girth at least ââ1, statement (i) holds for every mâ¥1; and observe that, statement (ii) also holds for every mâ¥1.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
F. Botler, G.O. Mota, M.T.I. Oshiro, Y. Wakabayashi,