Font Size: a A A

Decompositions Of The Complete Multipartite Multigraph Into Certain Five Vertex Graphs

Posted on:2003-03-05Degree:MasterType:Thesis
Country:ChinaCandidate:W ShuFull Text:PDF
GTID:2120360065460311Subject:Applied Mathematics
Abstract/Summary:PDF Full Text Request
Let λk_m1,m2,i...mn be the complete multipartite multigraph with vertexset where Vt(1 ≤i ≤ n) are disjoint sets with | Vt |= mt(i = 1,2,...,n) and where two vertices x and y from different sets Vt and Vj are joined by exactly λ edges. We write simply λK_n(g) for the complete multipartite multigraph with n-partite sets of size g, λK_g,g,...,g. When g = 1, λKn(g) is just the complete multigraph on n vertices, λKn.Given graph Hand G, let be a collection of subgraphs of G, each isomorphic to H. If the subgraphs of form a partition of the edge set of G, then (V(G),)is siad to be an H-decomposition of G.Recently, Hoffman and Kirkpatrick solved completely the problem for the existence of H-decompositions of λKn for certain five-vertex graphs. As a generalization, it is given in this paper the necessary and sufficient conditions for the existence of an H-decomposition of λKn(g).
Keywords/Search Tags:complete multipartite multigraph, graph decomposition, five-vertex graph
PDF Full Text Request
Related items