Research On The Existence Of Some Graph Decompositions

Let H be a, graph, and G a given subgraph of H. A G decomposition of H is a set of subgraphs of H whose edge sets partition the edge set of H, such that each subgraph is isomorphic to G. The graph decomposition problem plays an important role in cryptography, experiment design, X-ray diffraction crystallography, computer and communication network and other fields. With the development of graph theory becoming a systematic discipline gradually, people found that many combinatorial problems are closely related to the graph decomposition problem. In this paper, by using the combinatorial design theory, and applying the methods of recursive and direct constructions, we established the necessary and sufficient conditions for the existence of some graph decompositions.The whole thesis is organized as follows.In Chapter 1, we introduce the background, the definitions and some known results of graph decompositions, and present the main result of this thesis.In Chapter 2, in order to establish the existence of the following graph decompo-sitions, we give some recursive constructions.In Chapter 3, with the methods of recursive and direct constructions, we establish the necessary and sufficient conditions for the existence of metamorphosis of ?-fold P5-designs into maximum of A-fold P4-packings: ?v(v-1) = 0 (mod 8) and v?5.In Chapter 4, with the methods of recursive and direct constructions, we establish the necessary and sufficient conditions for the existence of metamorphosis of ?-fold K1,4-designs into maximum of A-fold K1,3-packings:?v(v-1)?0 (mod 8) and v?5.In Chapter 5, with the methods of recursive and direct constructions, we establish the necessary and sufficient conditions for the existence of metamorphosis of ?-fold C4 + e-designs into ?-fold P5-designs:?v(v-1)?0 (mod 40) and v?5.