×

The proportion of various graphs in graph-designs. (English) Zbl 1231.05025

Brualdi, Richard A. (ed.) et al., Combinatorics and graphs. Selected papers based on the presentations at the 20th anniversary conference of IPM on combinatorics, Tehran, Iran, May 15–21, 2009. Dedicated to Reza Khosrovshahi on the occasion of his 70th birthday. Providence, RI: American Mathematical Society (AMS) (ISBN 978-0-8218-4865-4/pbk). Contemporary Mathematics 531, 251-255 (2010).
Summary: Let \({\mathcal G}\) be a family of simple graphs. A \({\mathcal G}\)-design on \(n\) points is a decomposition of the edges of \(K_n\) into copies of graphs in \({\mathcal G}\). In case that \({\mathcal G}\) consists of complete graphs \(K_k\) with \(k\) in some set \(K\) of positive integers, such a \({\mathcal 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\in{\mathcal G}\) that appear in decompositions for large \(n\). We extend a result of C. J. Colbourn and V. Rödl [Discrete Math. 77, No. 1–3, 57–63 (1989; Zbl 0694.05009)] on PBDs to \({\mathcal G}\)-designs, and give a further result on the possible numbers of copies of \(G\) in a \({\mathcal G}\)-design containing each vertex of the complete graph \(K_n\).
For the entire collection see [Zbl 1202.05003].

MSC:

05B05 Combinatorial aspects of block designs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C35 Extremal problems in graph theory
05B30 Other designs, configurations

Citations:

Zbl 0694.05009
PDFBibTeX XMLCite