Factorizations of complete multipartite graphs into generalized cubes

For a positive integer d, the usual d-dimensional cube Q(d) is defined to be the graph (K-2)(d), the Cartesian product of d copies of K-2. We define the generalized cube Q(K-k, d) to be the graph (K-k)(d) for positive integers d and k. We investigate the decomposition of the complete multipartite graph Kk0 x kn-j into factors that are vertex-disjoint unions of generalized cubes Q(K-k, d(i)), where k is a power of a prime, n and j are positive integers with j less than or equal to n, and the d(i) may be different in different factors. We also use these results to partially settle a problem of Kotzig on Q(d)-factorizations of K-n. (C) 2000 John Wiley & Sons, Inc.