# Decomposition of complete graphs into paths and stars

*此作品的通信作者

研究成果: 雜誌貢獻期刊論文同行評審

30 引文 斯高帕斯（Scopus）

## 摘要

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.

原文 英語 2164-2169 6 Discrete Mathematics 310 15-16 https://doi.org/10.1016/j.disc.2010.04.009 已發佈 - 2010 8月 28

• 理論電腦科學
• 離散數學和組合

## 指紋

深入研究「Decomposition of complete graphs into paths and stars」主題。共同形成了獨特的指紋。