The proportion of various graphs in graph-designs

Abstract

Let G be a family of simple graphs. A G-design on n points is a decomposition of the edges of K_n into copies of graphs in G. In case that G consists of complete graphs K_k with k in some set K of positive integers, such a G-design is called a pairwise balanced design (PBD) on n points with block sizes from K. Here we are concerned with the possible proportions of the numbers of copies of graphs G ∈ G that appear in decompositions for large n. We extend a result of Colbourn and Rodl on PBDs to G-designs, and give a further result on the possible numbers of copies of G in a G-design containing each vertex of the complete graph K_n.

Files

Additional details