The (E)FTSM-(edge) Connectivity of Cayley Graphs Generated by Transposition Trees

The Cayley graph generated by a transposition tree Gamma(n) is a class of Cayley graphs that contains the star graph and the bubble sort graph. A graph G is called strongly Menger (SM for short) (edge) connected if each pair of vertices x,y are connected by min{d(G)(x),d(G)(y)} (edge)-disjoint paths, where d(G)(x),d(G)(y) are the degree of x and y respectively. In this paper, the maximally edge-fault-tolerant and the maximally vertex-fault-tolerant of Gamma(n) with respect to the SM-property are found and thus generalize or improve the results in [19, 20, 22, 26] on this topic.

Automated summary

This paper investigates the Cayley graph generated by a transposition tree and identifies the maximum edge and vertex fault tolerance with respect to the strong Menger connectivity. The results extend or improve upon previous research on this topic.