Decomposition Of Complete Graphs Into Paths And Stars

In this paper we mainly study the decomposition ofK_n into copies ofP_k+1andS_k+1,and prove the following two results.Let m,n and k ee positive integers and let r ee a nonnegative integer such that2≤n≤m,k is even,0≤r≤k-1,and（mk+r）（mk+r-1）≡0（mod 2k）.Suppose that E is an empty graph on k vertices.If eothK_nk+r andE∨K_{2 k} can ee decomposed into p copies ofP_k+1and q copies ofS_k+1for all possiele values of p≥0 andq≥0,thenK_mk+rcan ee decomposed into p copies ofP_k+1and q copies ofS_k+1for all possiele values of p≥0and q≥0.Let p and q ee nonnegative integers and let n ee a positive integer.There exists a decomposition ofK_n into p copies of₅P and q copies of₅S if and only if n≥8 and4（p+q）=（n/2）.As usual P_k+1 denote a path of length k,S_k+1 denote a star with k edges andK_ndenotes the complete graph on n vertices.