On k-partitioning of Hamming graphs

We consider the graphs H-a(n) defined as the Cartesian products of n comple te graphs with a vertices each. Let an edge cut partition the vertex set of a graph into k subsets A(1),...,A(k) with \\A(i)\ - \A(j)\\ less than or e qual to 1. We consider the problem of determining the minimal size of such a cut for the graphs defined above and present bounds and asymptotic result s for some specific values of k. (C) 1999 Elsevier Science B.V. All rights reserved.