Decomposition of complete bipartite graphs into paths and stars with same number of edges

Tay Woei Shyu*

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    17 Citations (Scopus)

    Abstract

    In this paper, we give some necessary and sufficient conditions for decomposing the complete bipartite graph Km, n into paths P k+1 and stars Sk+1 with k edges each. In particular, we find necessary and sufficient conditions for accomplishing this when m > k and n ≥ 3k, and we give a complete solution when k = 3. We also apply the results to show that for nonnegative integers p and q and positive integers n and k with n ≥ 4k, there exists a decomposition of the complete graph Kn into p copies of Pk+1 and q copies of Sk+ 1 if and only if k(p + q) = (n2).

    Original languageEnglish
    Pages (from-to)865-871
    Number of pages7
    JournalDiscrete Mathematics
    Volume313
    Issue number7
    DOIs
    Publication statusPublished - 2013 Apr 6

    Keywords

    • Complete bipartite graph
    • 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 bipartite graphs into paths and stars with same number of edges'. Together they form a unique fingerprint.

    Cite this