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 language | English |
---|---|
Pages (from-to) | 865-871 |
Number of pages | 7 |
Journal | Discrete Mathematics |
Volume | 313 |
Issue number | 7 |
DOIs | |
Publication status | Published - 2013 Apr 6 |
Keywords
- Complete bipartite graph
- Complete graph
- Decomposition
- Path
- Star
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics