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

Abstract

The k-ary n-cube, Q(n)(k) is one of the most popular interconnection networks. Let n >= 2 and k >= 3. It is known that Q(n)(k) is a nonbipartite (resp. bipartite) graph when k is odd (resp. even). In this paper, we prove that there exist r vertex disjoint paths {P(i) vertical bar 0 <= i <= r - 1} between any two distinct vertices u and v of Q(n)(k) when k is odd, and there exist r vertex disjoint paths {R(i) vertical bar 0 <= i <= r - 1} between any pair of vertices to and b from different partite sets of Q(n)(k) when k is even, such that boolean OR(r-1)(i=0) P(i) or boolean OR(r-1)(i=0) R(i) covers all vertices of Q(n)(k) for 1 <= r <= 2n. In other words, we construct the one-to-one r-disjoint path cover of Q(n)(k) for any r with 1 <= r <= 2n. The result is optimal since any vertex in Q(n)(k) has exactly 2n neighbors. (C) 2011 Elsevier B.V. All rights reserved.