Decompositions of complete graphs into paths and cycles

Tay Woei Shyu*

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    26 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


    • Complete graph
    • Cycle
    • Graph decompositions
    • Path

    ASJC Scopus subject areas

    • General Mathematics


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

    Cite this