One-to-one disjoint path covers on k-ary n-cubes

The k-ary n-cube, , is one of the most popular interconnection networks. Let n≥2 and k≥3. It is known that is a nonbipartite (resp. bipartite) graph when k is odd (resp. even). In this paper, we prove that there exist r vertex disjoint paths {Pi∣0≤i≤r−1} between any two distinct vertices u and v of when k is odd, and there exist r vertex disjoint paths {Ri∣0≤i≤r−1} between any pair of vertices w and b from different partite sets of when k is even, such that or covers all vertices of for 1≤r≤2n. In other words, we construct the one-to-one r-disjoint path cover of for any r with 1≤r≤2n. The result is optimal since any vertex in has exactly 2n neighbors.