The two-equal-disjoint path cover problem of Matching Composition Network

Embedding of paths have attracted much attention in the parallel processing. Many-to-many communication is one of the most central issues in various interconnection networks. A graph G is globally two-equal-disjoint path coverable if for any two distinct pairs of vertices (u, v) and (w, x) of G, there exist two disjoint paths P and Q satisfied that (1) P (Q, respectively) joins u and v (w and x, respectively), (2) vertical bar P vertical bar = vertical bar Q vertical bar, and (3) V(P boolean OR Q) = V(G). The Matching Composition Network (MCN) is a family of networks which two components are connected by a perfect matching. In this paper, we consider the globally two-equal-disjoint path cover property of MCN. Applying our result, the Crossed cube CQ(n), the TWisted cube TQ(n), and the Mobius cube MQ(n) can all be proven to be globally two-equal-disjoint path covetable for n >= 5. (C) 2007 Elsevier B.V. All rights reserved.