Orthogonal decomposition and packing of complete graphs

An H-decomposition of a graph G is a partition of the edge-set of G into su bsets, where each subset induces a copy of the graph H. A k-orthogonal H-de composition of a graph G is a set of k H-decompositions of G, such that any two copies of H in distinct,H-decompositions intersect in at most one edge . In case G=K-n and H=K-r, a k-orthogonal K-r-drcomposition of K-n is calle d an (n, r, k) completely reducible super-simple design. We prove that for any two fixed integers r and k, there exists N=N(k, r) such that for every n > N, if K-n has a K-r-decomposition. then K-n also has an (n, r, k) compl etely-reducible super-simple design. If K-n does not have a K-r-decompositi on, we show how to obtain a k-orthogonal optimal K-r-packing of K-n. Comple xity issues of k-orthogonal H-decompositions are also treated. (C) 1999 Aca demic Press.