TY - JOUR
T1 - Decomposition of complete bipartite graphs into paths and stars with same number of edges
AU - Shyu, Tay Woei
N1 - Funding Information:
I am so thankful for the referees’ helpful comments. The research was supported by NSC of ROC under grant NSC 97-2115-M-003-006 .
PY - 2013/4/6
Y1 - 2013/4/6
N2 - 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).
AB - 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).
KW - Complete bipartite graph
KW - Complete graph
KW - Decomposition
KW - Path
KW - Star
UR - http://www.scopus.com/inward/record.url?scp=84893688111&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84893688111&partnerID=8YFLogxK
U2 - 10.1016/j.disc.2012.12.020
DO - 10.1016/j.disc.2012.12.020
M3 - Article
AN - SCOPUS:84893688111
SN - 0012-365X
VL - 313
SP - 865
EP - 871
JO - Discrete Mathematics
JF - Discrete Mathematics
IS - 7
ER -