Path decompositions of regular graphs with prescribed girth

• DOI: 10.1016/j.endm.2015.06.085
• Publication Date: 2015-11-12T21:38:36Z
• Authors: F. Botler; G.O. Mota; M.T.I. Oshiro; Y. Wakabayashi
• Keywords: Odd graph; Girth (graph theory); Disjoint sets

A Pl-decomposition of a graph G is a set of pairwise edge-disjoint paths of G with l edges that cover the edge set of G. Kotzig [Kotzig, A., Aus der Theorie der endlichen regularen Graphen dritten und vierten Grades, Casopis Pěst. Mat. 82 (1957), pp. 76–92.] 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 l-regular graph to admit a Pl-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 ml-regular graph with girth at least g that contains an m-factor admits a Pl-decomposition; (ii) if m>⌊(l−2)/(g−2)⌋, then every 2ml-regular graph with girth at least g admits a Pl-decomposition.