Cycle decompositions V: Complete graphs into cycles of arbitrary lengths. Issue 5 (16th October 2013)

• Record Type: Journal Article
• Authors: Bryant, Darryn; Horsley, Daniel; Pettersson, William
• Is Part Of: Proceedings of the London Mathematical Society. Volume 108:Issue 5(2014:May)
• Page Start: 1153
• Page End: 1192
• Publication Date: 2013-10-16
• Subjects: Mathematics -- Periodicals; Mathematics; Periodicals; 510
• DOI: 10.1112/plms/pdt051
• Languages: English
• ISSNs: 0024-6115

Abstract

Abstract : We show that the complete graph on n vertices can be decomposed into t cycles of specified lengths m 1, …, m t if and only if n is odd, 3⩽ m i ⩽ n for i =1, …, t, andm 1 + ⋯ + m t = ( n 2 ) . We also show that the complete graph on n vertices can be decomposed into a perfect matching and t cycles of specified lengths m 1, …, m t if and only if n is even, 3⩽ m i ⩽ n for i =1, …, t, andm 1 + ⋯ + m t = ( n 2 ) − n / 2 .