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 Qnk 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, Qnk has m disjoint (S,T)-paths containing all vertices of Qnk and our result is optimal.