The edge fault-tolerant two-disjoint path covers of Cayley graphs generated by a transposition tree.

Given a graph G , let S and T be two disjoint vertex subsets of equal size k in G. A many-to-many k -disjoint path cover of G joining S and T is a set of k vertex-disjoint paths between S and T that altogether cover every vertex of the graph. It is said to be paired if each vertex of S must be joined to a designated vertex of T , or unpaired otherwise. Let Γ n be a Cayley graph generated by a transposition tree with bipartition V 0 and V 1. Let S ⊆ V 0 and T ⊆ V 1 be two vertex subsets of equal size two. It is shown in this paper that Γ n has an unpaired many-to-many two-disjoint path cover joining S and T with at most n − 4 faulty edges, where n ≥ 4. The result is optimal with respect to the degree of Γ n. As applications, the edge fault-tolerant two-disjoint path covers for the star network, bubble-sort network and modified bubble-sort network are derived. [ABSTRACT FROM AUTHOR]