Six Graph Design

A complete multigraph with order v and index A, denoted by Kv, is an undirected graph with v vertices, where any two distinct vertices x and y are joined by A edges (x,y). Let G be a finite simple graph. A graph design G-GD(v) is a pair (X, B), where X is the vertex set of Kv and B is a partition of all edges in Kv, such that each member (block) of B is a subgraph of Kv, isomophic to G.In this dissertation, we discuss the existence problems of graph design for six graphs with six vertices and nine edges.In Chapter 1, some concepts are introduced, such as G-design, holey G-design and incomplete G-design. And, the necessary condition to exist G-design for the six graphs G is listed. As well as, two basic lemmas are rewrited.In Chapter 2, construct some holey G-designs using quasigroups and directed product automorphism group as well as other methods.In Chapter 3, list the arrangement to complete the graph designs for each graph, respectively.In Chapter 4, study the existence for some graph designs and prove that Gk-GD(9)(k= 2,3,4,5,6) and G3-GD3(6) do not exist. As well as, construct all graph designs listed in Chapter 3.In Chapter 5. construct all incomplete G-designs listed in Chapter 3.In Chapter 6, obtain our main conclusions:There exist Gk-GD(v)= v(v - 1) = 0 (mod 18), v > 6, except G3-GD3(6) and Gk-GD(9) for k= 1,3,4,5,6, and G6-GD(18t+ 10) exist for t > 0 if there exists G6-GD(v) for each v in A = {64,82,100,136,154,190,208,244,262,316,370,424} .