Decomposing complete graphs into K-r x K-c's

Abstract

We consider the problem of decomposing a complete graph into the Cartesian product of two complete graphs K, and K, This problem originated from the clone library screening. We give a general method of constructing such decompositions using various sorts of combinatorial designs. In particular, for r = 3 and c = 3, we show that such a decomposition exists for all n satisfying some simple necessary conditions. (C) 2002 Elsevier B.V. All rights reserved.