Decomposing regular graphs with prescribed girth into paths of given length

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.