Decomposition of complete graphs into paths of length three and triangles

Tay Woei Shyu*

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    15 Citations (Scopus)

    Abstract

    Let Pk+1 denote a path of length k and let C k denote a cycle of length k. A triangle is a cycle of length three. As usual Kn denotes the complete graph on n vertices. It is shown that for all nonnegative integers p and q and for all positive integers n, Kn can be decomposed into p copies of P4 and q copies of C3 if and only if 3(p + q) = e(Kn), p ‡1 if n is odd, and p ≥ n/2 1/2 n is even.

    Original languageEnglish
    Pages (from-to)209-224
    Number of pages16
    JournalArs Combinatoria
    Volume107
    Publication statusPublished - 2012 Oct

    ASJC Scopus subject areas

    • General Mathematics

    Fingerprint

    Dive into the research topics of 'Decomposition of complete graphs into paths of length three and triangles'. Together they form a unique fingerprint.

    Cite this