The Metamorphosis Of Two Bipartite Graph Designs Into Subgraph Designs

Let Kv be a complete graph of order v, and G a finite simple graph. A graph design G-GDλ(v)(graph packing G-PDλ(v), graph covering G-CDλ(v)) is a pair (X,B), where X is the vertex set of Kv and B is a collection of subgraphs of Kv, called blocks, such that each block is isomorphic to G and each edge in Kv occurs in exactly(at most, at least) λ blocks of B. A graph packing (or covering) is said to be maximum (or minimum) if no other such graph packing (or covering) with the same order has more (or fewer) blocks, denoted by max G-PDλ(v)(min G-CDλ(v)). The number of blocks in a maximum G-packing (or minimum G-covering) is denoted by p(v, G, λ)(or c(v, G, λ)). A G-PDλ(v)(or G-CDλ(v)) is said to be regular if denoted by G-OPDλ(v)(G-OCDλ(v)).Let (X, B) be a G-GDλ(v) and H a subgraph of G. For each block B E∈B, partition B into B’ and B\B’, where B’ is isomorphic to H. Define B(H)={B’:B E∈B}. If the edges in D(G\H)={B\B’:B E∈B} can be reassembled into a collection D(H) of copies of H, then (X,B(H) ∪ D(H)) is an H-GDλ(v). The procedure above is called a metamorphosis of G-GDλ(v) into H-GDλ(v) and denoted by (G> H)-GMλ(v).In this thesis, the spectrums of metamorphosis of two bipartite graph designs into subgraph designs are determined. Meanwhile, the problems of graph design, optimal packing design and optimal covering design of 4 graphs with seven vertices and seven edges are solved completely.