Let v [greater than or equal to] k [greater than or equal to] 1 and lamda [greater than or equal to] 0 be integers and G be a graph with n vertices, m edges, and no multiple edges. A (v, k, lambda) block design is a collection Beta of k-subsets of a v-set X in which every unordered pair of elements in X is contained in exactly lambda of the subsets in Beta. A (G-decomposition, or (v, G, lambda) graph design, is a collection H1, H2, ..., Ht of subgraphs of Kv (the complete graph on v vertices) such that each edge of Kv is an edge of exactly lambda of the subgraphs Hi and each of the subgraphs Hi is isomorphic to G. A famous result by Wilson says that for a fixed graph G and integer lambda, there exists a (v, G, lambda) graph design for all sufficiently large integers v satisfying certain necessary conditions. In this thesis, we extend this result to include the case of loops in G. As a consequence, one obtains asymptotic existence of equireplicate graph designs for values of v satisfying certain necessary conditions, where a graph design is called equireplicate if each vertex of Kv occurs in the same number of subgraphs Hi of the decomposition.
| Identifer | oai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/1705 |
| Date | 31 August 2009 |
| Creators | Malloch, Amanda |
| Contributors | Dukes, Peter |
| Source Sets | University of Victoria |
| Language | English, English |
| Detected Language | English |
| Type | Thesis |
| Rights | Available to the World Wide Web |
Page generated in 0.0026 seconds