Decomposition of Complete Graphs into Cycles and Stars

Tay Woei Shyu*

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    29 Citations (Scopus)


    Let Ck denote a cycle of length k and let Sk denote a star with k edges. As usual Kn denotes the complete graph on n vertices. In this paper we investigate decomposition of Kn into Cl's and Sk's, and give some necessary or sufficient conditions for such a decomposition to exist. In particular, we give a complete solution to the problem in the case l = k = 4 as follows: For any nonnegative integers p and q and any positive integer n, there exists a decomposition of Kn into p copies of C4 and q copies of S4 if and only if 4(p + q) = q ≠ 1 if n is odd, and q ≥{3, n/2}if n is even.

    Original languageEnglish
    Pages (from-to)301-313
    Number of pages13
    JournalGraphs and Combinatorics
    Issue number2
    Publication statusPublished - 2013 Mar


    • Complete graph
    • Cycle
    • Graph decomposition
    • Star

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Discrete Mathematics and Combinatorics


    Dive into the research topics of 'Decomposition of Complete Graphs into Cycles and Stars'. Together they form a unique fingerprint.

    Cite this