Large Set Of Graph Design

Let G be a finite simple graph (or digraph). The so-called graph design for G or G-decomposition, denoted by (v,G,X)-GD or G-GD(v), is a pair (X,B) , where A' is the vertex set of Kv (or DKV) and B is a collection of subgraphs of Kv (or DKv), called blocks, such that each block is isomorphic to G and each edge (or arc) of Kv (or DKV) appears exactly A times in B.A large set of (v,G,\)-GD, denoted by (v,G,X)-LGD or G-LGDx{v), is a partition B1, B2. ..., Bm of all subgraphs(each subgraph is isomorphic to G) in Kv or DKV (if G is a digraph) such that each B3 (1 < j < m) is a (v, G, X)-GD.In this dissertation, we discuss the existence problem of large set of graph design.In Chapter 1. we introduce some terminologies and basic concepts, give some known results about graph design and its large set and list the main questions we discuss and the main conclusions we draw in the paper.In Chapter 2, we investigate the existence of (v,Pi3,X)-GD and (v,Pi3, X)-LGD, where Pi3 (i = 1,2,3) are there types of oriented path with 3 vertices. At first, we discuss all the block-orbits on the given vertex set, then we partition all the block-orbits into some parts according to the unordered differences they contain, at last, we obtain the existence spectrums of (v, Pi3 X)-GD and (v, Pi3, X)-LGD(i = 1,2,3) by using direct constructions and recursive method.In Chapter 3, we do some research on (v, Pk, X)-LGD for the path Pk. We obtain a general result by using finite fields, that is, if q > k > 2 is an odd prime power, then there exists a (q, Pk, k -1)-LGD. In addition, for the path P4, we continue to discuss (v,P4 )-LGD. we give all the block-orbits on the given vertex set and obtain some results about large sets.In Chapter 4, we aim at solving the existence problem of (v, K1,3, X)-LGD for the star K1,3. We discuss all the block-orbits on the given vertex set. All the block-orbits are partitionted into some parts, by using the parts we construct (v, K1,3, Z)-LGD for v = 5 (mod 6). Furthermore, we solve the existence problem of (v,K1,3,X)-LGD forv = 5 (mod 6). We provide a method to construct a (v, K1,3, 3)-LGD for v = 2 (mod 6), by using this method we give the constructions of some large sets.In Chapter 5, we discuss the existence problem of (v, K1,4, X)-LGD for the star K1,4. All the block-orbits on the given vertex set are investigated. We partition all the block-orbits into some parts, using the parts, we solve the existence of (v.K1,4,4)-LGD for v = 3 (mod 4). Furthermore, we obtain the existence spectrum of (v, K1,4, X)-LGD for v = 3 (mod 4). For some other types of parameters, we give the relevant large sets.In Chapter 6, we do some elementary research on (v,C4,)-LGD, where C4 is a cycle of length 4. We give the classification and the enumeration of all the block-orbits on the given vertex set. We provide a method, that is, all the block-orbits will be partitioned into some parts under the action of a multiplication map. By using this method, we give some results of (v,C4,4)-LGD for v = 3 (mod 4). In addition, we also give some more examples.