Decompositions of complete graphs into paths and cycles

Tay Woei Shyu*

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

21 Citations (Scopus)


Abstract. Let Pk+1 denote a path of length k and let C k denote a cycle of length k. As usual Kn denotes the complete graph on n vertices. In this paper we investigate decompositions of Kn into paths and cycles, and give some necessary and/or sufficient conditions for such a decomposition to exist. Besides, we obtain a necessary and sufficient condition for decomposing Kn into p copies of P 5 and q copies of C4 for all possible values of p ≥ 0 and q ≥ 0.

Original languageEnglish
Pages (from-to)257-270
Number of pages14
JournalArs Combinatoria
Publication statusPublished - 2010 Oct 1


  • Complete graph
  • Cycle
  • Graph decompositions
  • Path

ASJC Scopus subject areas

  • Mathematics(all)


Dive into the research topics of 'Decompositions of complete graphs into paths and cycles'. Together they form a unique fingerprint.

Cite this