摘要： BIBD (Balanced Incomplete Block Designs) as combinatorial objects, arose in statistics. The classical BIBD(n) is a decomposition of {1, 2,…, n} into triples such that every pair {xi, xj} occurs in exactly one triple. Two natural extensions of this notion are to have every pair appear in _ triples or decompose{1, 2,…, n} into quadruples or larger subsets.

From a graph theoretic point of view, we are trying to decompose the complete graph Kn into triangles K3 (or more generally, Kr) so that every edge appears in one triangle (Kr) or do the same for mKn (every edge is replaced by m parallel edges).

The next natural generalization is decomposition of Kn into copies of a given graph G. These are called graph designs. If G happens to be of size n such a decomposition is called a spanning graph design. One of the major tools for tackling these problem are various graph labeling.

In this talk I plan to give a survey of spanning graph designs and present many simply formulated yet challenging problems.