An existence theory for loopy graph decompositions

✍ Scribed by Peter Dukes; Amanda Malloch

• Publisher: John Wiley and Sons
• Year: 2011
• Tongue: English
• Weight: 118 KB
• Volume: 19
• Category: Article
• ISSN: 1063-8539
• DOI: 10.1002/jcd.20280

✦ Synopsis

Let v ≥ k ≥ 1 and k ≥ 0 be integers. Recall that a (v, k, k) block design is a collection B of k-subsets of a v-set X in which every unordered pair of elements in X is contained in exactly k of the subsets in B. Now let G be a graph with no multiple edges. A (v, G, k) graph design is a collection H of subgraphs, each isomoprhic to G, of the complete graph K v such that each edge of K v appears in exactly k of the subgraphs in H. A famous result of Wilson states that for a fixed simple graph G and integer k, there exists a (v, G, k) graph design for all sufficiently large integers v satisfying certain necessary conditions. Here, we extend this result to include the case of loops in G. As a consequence, we obtain the asymptotic existence of equireplicate graph designs. Applications of the equireplicate condition are given.