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

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\) whose unions cover every vertex of \(G\). It is said to be paired if each vertex of \(S\) must be joined to a prescribed vertex of \(T\), or unpaired otherwise.\N\NA graph \(G\) is many-to-many \(k\)-disjoint path coverable (\(k\)-disjoint path coverable for short) if, for any two disjoint vertex subsets \(S\) and \(T\) of equal size \(k\) in \(G\), there is a many-to-many \(k\)-disjoint path cover between them. Moreover, a graph \(G\) is said to be \(f\)-edge fault-tolerant \(k\)-disjoint path coverable if there still exists such a path cover after removing any edges from \(G\) whose cardinality is not more than \(f\).\N\NIn this paper, it is shown that for \(n\geq 4\), an \(n\)-dimensional Cayley graph of the symmetry group \(S_n\) generated by a transposition tree is \((n-4)\)-edge fault-tolerant unpaired two-disjoint path coverable. The result is best possible with respect to the degree of the graph. As an interesting corollary, the edge fault-tolerant two-disjoint path covers for the star network, the bubble-sort network and the modified bubble-sort network are derived.