Decomposition of complete graphs into paths and stars

Tay Woei Shyu*

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    30 Citations (Scopus)

    Abstract

    Let Pk + 1 denote a path of length k and let Sk + 1 denote a star with k edges. As usual Kn denotes the complete graph on n vertices. In this paper we investigate the decomposition of Kn into paths and stars, and prove the following results. Theorem A. Let p and q be nonnegative integers and let n be a positive integer. There exists a decomposition of Kn into p copies of P4 and q copies of S4 if and only if n ≥ 6 and 3 (p + q) = fenced(frac(n, 2)). Theorem B. Let p and q be nonnegative integers, let n and k be positive integers such that n ≥ 4 k and k (p + q) = fenced(frac(n, 2)), and let one of the following conditions hold: (1)k is even and p ≥ frac(k, 2),(2)k is odd and p ≥ k. Then there exists a decomposition of Kn into p copies of Pk + 1 and q copies of Sk + 1.

    Original languageEnglish
    Pages (from-to)2164-2169
    Number of pages6
    JournalDiscrete Mathematics
    Volume310
    Issue number15-16
    DOIs
    Publication statusPublished - 2010 Aug 28

    Keywords

    • Complete graph
    • Decomposition
    • Path
    • Star

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Discrete Mathematics and Combinatorics

    Fingerprint

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

    Cite this