TY - JOUR
T1 - Decomposition of complete graphs into paths and stars
AU - Shyu, Tay Woei
N1 - Funding Information:
I am so thankful for the referees’ helpful comments. The research was supported by the National Science Council under grant NSC 96-2115-M-003-005 .
PY - 2010/8/28
Y1 - 2010/8/28
N2 - 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.
AB - 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.
KW - Complete graph
KW - Decomposition
KW - Path
KW - Star
UR - http://www.scopus.com/inward/record.url?scp=77953128324&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=77953128324&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2010.04.009
DO - 10.1016/j.disc.2010.04.009
M3 - Article
AN - SCOPUS:77953128324
SN - 0012-365X
VL - 310
SP - 2164
EP - 2169
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 15-16
ER -