Path decompositions of γKn,n

Tay Woei Shyu*

*Corresponding author for this work

    Research output: Contribution to journalArticlepeer-review

    3 Citations (Scopus)


    Let Pk denote a path with k vertices and k - 1 edges. And let γKn,n denote the γ-fold complete bipartite graph with both parts of size n. A Pk-decomposition D of γKn,n is a family of subgraphs of γKn,n whose edge sets form a partition of the edge set of XKn-n such that each member of & is isomorphic to Pk. Necessary conditions for the existence of a Pfc-decomposition of γKn,n are (i) γn2 = 0 (mod k-1) and (ii) k ≤ n + 1 if γ = 1 and n is odd, or k ≤ 2n if A ≥ 2 or n is even. In this paper, we show these necessary conditions are sufficient except for the possibility of the case that γ = 3, n = 15, and k = 28.

    Original languageEnglish
    Pages (from-to)211-219
    Number of pages9
    JournalArs Combinatoria
    Publication statusPublished - 2007 Oct

    ASJC Scopus subject areas

    • General Mathematics


    Dive into the research topics of 'Path decompositions of γKn,n'. Together they form a unique fingerprint.

    Cite this