An existence theory for loopy graph decompositions

Let v≥k≥1 and λ≥0 be integers. Recall that a (v, k, λ) block design is a collection ℬof k‐subsets of a v‐set X in which every unordered pair of elements in X is contained in exactly λ of the subsets in ℬ. Now let G be a graph with no multiple edges. A (v, G, λ) graph design is a collection ℋof subgraphs, each isomoprhic to G, of the complete graph K v such that each edge of K v appears in exactly λof the subgraphs in ℋ. A famous result of Wilson states that for a fixed simple graph G and integer λ, there exists a (v, G, λ) 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. Copyright © 2011 Wiley Periodicals, Inc. J Combin Designs 19:280‐289, 2011