Paths And Stars Decompositions Of Some Graphs

All graphs considered here are finite and undirected.A graph G is an ordered pair(V(G),E(G)),where V(G)and E(G)are the vertex set and edge set of the graph G,respectively.Kn denotes the complete graph of order n and Km,n denotes the complete bipartite graph with parts of sizes m and n,respectively.Let Pk+1 denote a path with k edges and Sk+1 denote a star with k edges.An H-decomposition of G is a partition of the edge set of G into copies of H which is a subgraph of G.If the graph H is a path,we say that G is path H-decomposable.If the graph H=H1?H2 and E(H1)?E(H2)=(?),we say that G is(H1,H2)-decomposable.The paper considers paths and stars-decomposition of the complete bipartite graphs,the complete graphs and the complete graphs with a hole which can be found the following four chapters.In the first chapter,a short survey of Pk+1 or Sk+1 decomposition of Kn and Km,n are given.In the second chapter,first we consider the necessary and sufficient conditions of paths Pk+3 and stars Sk+i decomposition of the complete bipartite graph Kk,n.Second we get the sufficient conditions of paths Pk+3 and stars Sk+1 decomposition of the complete bipartite graph Kmk,n.At last,we acquire the sufficient conditions of paths Pk+3 and stars Sk+1 decomposition of the complete bipartite graph Km,n.In the third chapter,we give the sufficient conditions of complete graph Kn decom-posed into paths Pk+3 and stars Sk+1 when s and k are even number more than 2 and t is less than s/2 n=sk,n=sk+1,n=sk+4t and n=sk+4t+1.In the fourth chapter,we prove that the split graph Km+n-Kn can be decomposed into the paths Pk+3 and stars Sk+1 when s and k are even numbers,s>2,k>2,i is positive integers,t?s/2,m?k+2/x,n=sk or m=ik,n=sk+1.We also give the sufficient conditions of paths Pk+3 and stars Sk+i decomposition of the split graph Km+n-Km where k is even number,k?2,s is a positive even number,i and t are positive integers,t?s/2,m=ik,n=sk+4t or n=sk+4t+1.