Decomposition of complete graphs into paths and stars

作者：Shyu Tay Woei^*

来源：Discrete Mathematics, 2010, 310(15-16): 2164-2169.

DOI：10.1016/j.disc.2010.04.009

• Decomposition
• Path
• Star
• Complete graph

Let P(k+1) denote a path of length k and let S(k+1) denote a star with k edges. As usual K(n) denotes the complete graph on n vertices. In this paper we investigate the decomposition of K(n) 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 K(n) into p copies of P(4) and q copies of S(4) if and only if n >= 6 and 3(p + q) = (n/2).
Theorem B. Let p and q be nonnegative integers, let n and k be positive integers such that n >= 4k and k(p + q) = (n/2), and let one of the following conditions hold:
(1) k is even and p >= k/2,
(2) k is odd and p >= k.
Then there exists a decomposition of K(n) into p copies of P(k+1) and q copies of S(k+1).

• 出版日期2010-8-28