Narrow Results

The Cayley graph generated by a transposition tree ${\mathrm{\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 ${\mathrm{\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.

The local connectivity of two vertices is defined as the maximum number of internally vertex-disjoint paths between them. In this paper, we define two vertices as maximally local-connected, if the maximum number of internally vertex-disjoint paths between them equals the minimum degree of these two vertices. Moreover, we show that an (n-1)-regular Cayley graph generated by transposition tree is maximally local-connected, even if there are at most (n-3) faulty vertices in it, and prove that it is also (n-1)-fault-tolerant one-to-many maximally local-connected.