Graph Decompositions And Related Problems

Let H be a graph and g be a set of simple graphs.By a decomposition of a graph H we mean a partition of its edge-set.If a graph H can be decomposed into edge disjoint subgraphs each of which is isomorphic to a graph of g,then we say that the decomposition is an(H,g)-decomposition.If g contains a single graph G,we speak of an(H,G)-decomposition.The problems discussed in this thesis are closely related to graph decomposition.Graph packing,graph covering and graph embedding are important problems in the direction of graph decompositon.In this thesis,we figure out all possible leaves in(K4-e)-MGDPs of type gn for any g>1,and examine all possible excesses for simple(K4-e)-MGDCs of type g".On the basis of minimum embedding of STSs into(K3+ e)-designs,we determine that the necessary conditions of a STS(V,B)embedded into a(K3 + e)-design(V ? W,C)are sufficient for the second minimum |V ? W|.What is more,the concept of group divisible nuclear design is introduced,and we discuss the existence of(K4-e)-GDNDs of type gn.This thesis is organized as follows.Chapter 1 gives a brief introduction on the background and basics of graph decom-positon and the main result of this thesis.In Chapter 2,we discuss the construction of(K4-e)-IGDDs of type g(n,h)and(g,h)n,respectively.In Chapter 3,we first give the nonexistence proof of(K4-e)-MGDPs with several specific parameters.Second,we obtain some small order results of(K4-e)-MGDPs by using direct and recursive construction methods.In the end,by applying the con-struction methods of(K4-e)-MGDPs and combining the existence of the two kinds of(K4-e)-IGDDs,we prove that all possible leaves could be obtained in(K4-e)-MGDPs of type gn for any g>1.In Chapter 4,we first discuss the relationship between(K4-e)-MGDPs and(K4-e)-MGDCs,and then the combinatorial tools in the proof process are reviewed and explained.Next we obtain some small order results of(K4-e)-MGDCs by using direct and recursive construction methods.In the end,by applying the construction methods of(K4-e)-MGDCs and combining the existence of the two kinds of(K4-e)-IGDDs,we examine all possible excesses for simple(K4-e)-MGDCs of type gn.In Chapter 5,graph embedding is introduced,and on the basis of minimum em-bedding of STSs into(K3 + e)-designs,we determine that the necessary conditions of a STS(V,B)embedded into a(K3 + e)-design(V?W,C)are sufficient for the second minimum |V ? W|.In Chapter 6,the concept of group divisible nuclear design is introduced.we dis-cuss the existence of(K4-e)-MGDPs and(K4-e)-MGDCs of type gn by using direct and recursive construction methods.Then we determin the existence of(K4-e)-GDNDs of type gn.