Decomposing regular graphs with prescribed girth into paths of given length. (December 2017)

• Record Type: Journal Article
• Authors: Botler, F.; Mota, G.O.; Oshiro, M.T.I.; Wakabayashi, Y.
• Is Part Of: European journal of combinatorics. Volume 66(2017)
• Page Start: 28
• Page End: 36
• Publication Date: 2017-12
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2017.06.011
• Languages: English
• ISSNs: 0195-6698

Abstract

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 P 3 -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 2 m ℓ -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 .