Graph Design, Packing And Covering Of Twelve Graphs With Nine Vertices And Nine Edges

For a finite simple graph G, a G-design (G-packing design, G-covering design) of λKv denoted by G-GDλ(v)(G-PDλ(v), 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 iso-morphic to G and any two distinct vertices in Kv are jointed in exactly (at most, at least) λ blocks of B. A G-packing (G-covering) is said to be maximum (minimum), denoted by max G-PDλ(v) (min G-CDλ(v) ), if no other such G-packing (G-covering) has more (fewer) blocks. The number of blocks in a maximum G-packing (minimum G-covering), denoted by p(v, G, λ) (c(v, G, λ)), is called the packing (covering) number. It is well known that p (v, G, λ)≤「(λv(v-1))/(2|E(G)|)」≤「(λv(v-1))/(2|E(G)|)」≤c(v,G,λ), where E(G) denotes the number of edges in G, 「x」 (「x」) denotes the greatest (least) integer y such that y≤x(y≥x). A G-PDλ(v)(G-CDλ(v)) is said to be optimal and denoted by G-OPDλ(v)(G-OCDλ(v)) if the left (right) equality holds. In this thesis, the spectrum of the existence of Gi-GDλ(v) is determined, and the optimal packing designs and optimal covering designs are obtained, here Gi denotes a graph with nine vertices and nine edges, 1≤i≤12.