Paired 2-disjoint path covers of multidimensional torus networks with faulty edges ?
A paired k-DPC of a graph is a set of k disjoint paths joining k source-sink pairs that cover all vertices of the graph. Let T=T(k1,k2,,kn) T = T ( k 1 , k 2 ,  , k n ) be a torus and F be a set of faulty edges in T. Let |F|?2n?3 | F | ? 2 n ? 3 and even ki?4 k i ? 4 for all i . Then T?F T ? F has a paired 2-DPC if each partite set contains two end-vertices. Let |F|?2n?4 | F | ? 2 n ? 4 and odd ki?3 k i ? 3 for all i  with at most one even kj k j . Then T?F T ? F has a paired 2-DPC. Our brief proofs are based on a technique that is of interest and may find some applications.
multidimensional torus paired disjoint path cover fault-tolerance cartesian product of graphs interconnection network