On the Two-Equal-Disjoint Path Cover Problem of Twisted Cubes

Abstract

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 (x, y) of G, there exist two disjoint paths Puv and Pxy satisfied that (1) Puv joins u to v and Pxy joins x to y, (2) |Puv| = |Pxy|, and (3) V (Pxy SPxy) = V (G). In this paper, we prove that TQn is globally 2-equal-disjoint path coverable for n ≥ 5.