Resolvable G-decompositions Of Complete Multipartite Graph For Graphs With Four Vertices

Graph decomposition is an important research object in combinatorial design and graph theory.In this thesis we mainly study resolvable graph designs for two graphs with four vertices,namely-D3(4)and K4-e,including resolvable group divisible designs,frames,maximum resolvable packings and minimum resolvable coverings.Let H be a complete u-partite graph whose vertex set can be partitioned into u parts M1,M2,...,Mu of size g.If E(AH)can be partitioned into parallel classes of H(partial parallel classes of H-V(Mi)(1?i?u),and each subgraph is isomorphic to a graph G,then it is called a resolvable divisible G-design(G-frame)of type gu with index ?,denoted by(G,?)-RGDD(gu)((G,?)-F(gu)).A G-packing(covering)of Kv is a pair(X,B),where X is the vertex set of Kv and B is a collection of subgraphs isomorphic to G in Kv such that each edge of Kv appears at most(at least)once in the subgraphs.A G-packing(covering)(X,B)is called resolvable if the block set B can be partitioned into parallel classes.A resolvable G-packing(covering)is called maximum(minimum)if it has maximum(minimum)possible number of parallel classes.The existence of resolvable group divisible designs and frames for graphs with four vertices have been extensively studied.Except for D3(4),K4-e and K4,all the other cases have been solved.Since 2007,Ge and Wang et al.have studied the existence of a(G,1)-RGDD(gu)and a(G,1)-F(gu)with G as D3(4)and K4-e,re-spectively,leaving some infinite classes unsolved.Wang et al.gave the construction of maximum resolvable packings and minimum resolvable coverings of K4-e with 11 possible exceptions.In this thesis,algebraic and combinatorial methods are used to solve the exis-tence of a(G,?)-F(gu)for all ? and G ?D3(4),K4-e},and the existence of a(D3(4),?)-RGDD(gu),and we almost completely solve the existence of a(K4-e,?)-RGDD(gu).We also solve the 11 possible exceptions of the maximum resolvable packing and minimum resolvable covering of K4-e.