Decomposing regular graphs with prescribed girth into paths of given length

A P l -decomposition of a graph G is a set of pairwise edge-disjoint paths with l edges that cover the edge set of G . In 1957, Kotzig proved that a 3 -regular graph admits a P 3 -decomposition if and only if it contains a perfect matching, and also asked what are the necessary and sufficient conditions for an l -regular graph to admit a P l -decomposition, for odd l . Let g , l and m be positive integers with g ≥ 3 . We prove that, (i) if l is odd and m > 2 ⌊ ( l − 2 ) ∕ ( g − 2 ) ⌋ , then every m l -regular graph with girth at least g that contains an m -factor admits a P l -decomposition; (ii) if m > ⌊ ( l − 2 ) ∕ ( g − 2 ) ⌋ , then every 2 m l -regular graph with girth at least g admits a P l -decomposition. Furthermore, we prove that, for graphs with girth at least l − 1 , statement (i) holds for every m ≥ 1 ; and observe that, statement (ii) also holds for every m ≥ 1 .