Paired 2-disjoint path covers of multi-dimensional torus networks with 2n − 3 faulty edges.

The n -dimensional torus T ( k 1 , k 2 , … , k n ) (including the k -ary n -cube Q n k ) is one of the most popular interconnection networks. A paired k -disjoint path cover (paired k -DPC for short) of a graph is a set of k disjoint paths joining k distinct source-sink pairs that cover all vertices of the graph. In this paper, we consider the paired 2-DPC problem of n -dimensional torus. Assuming k i ≥ 3 for i = 1 , 2 , … , n , with at most one k i being even, then T ( k 1 , k 2 , … , k n ) with at most 2 n − 3 faulty edges always has a paired 2-DPC. And the upper bound 2 n − 3 of edge faults tolerated is optimal. The result is a supplement of the results of Chen [3] and [4] . [ABSTRACT FROM AUTHOR]