Many-to-many disjoint path covers in k-ary n-cubes

The class of k-ary n-cubes represents the most commonly used interconnection topology for parallel and distributed computing systems. Embedding of disjoint paths has attracted much attention in the parallel processing. In disjoint path problems, the many-to-many disjoint path problem is the most generalized one. This paper considers the problem of many-to-many disjoint path covers in the k-ary n-cube Q(n)(k) with even k >= 4, and obtains the following result. Let m be an integer with 1 <= m <= 2n - 1. For any two sets S and T of m vertices in different partite sets, Q(n)(k) has m disjoint (S, T)-paths containing all vertices of Q(n)(k) and our result is optimal. (C) 2013 Elsevier B.V. All rights reserved.