Component connectivity of Cayley graphs generated by transposition trees. Issue 1 (2nd January 2020) - Xu, Liqiong; Zhou, Shuming; Yang, Weihua
ABSTRACT: Connectivity is an important measure to explore the fault tolerance and reliability of the network structure based on a graph model. Let G = ( V, E ) be a connected graph. A r -component cut of G is a set S of vertices, G − S has at least r components. The r -component connectivity c κ r ( G ) of G is the size of the smallest r -component cut. The r -component edge connectivity c λ r ( G ) can be defined similarly. In this paper, we determine the r -component connectivity of Cayley graphs generated by transposition trees c κ r + 1 ( T n ) = r ( n − 1 ) − r ( r + 1 ) / 2 + 1 for r = 1, 2, …, n − 1 and n ≥ 3 ; we also obtain the r -component edge connectivity of Cayley graphs generated by transposition trees T n for small r and the upper and lower bounds of c λ r + 1 ( T n ) for r = 1, 2, …, n − 1 and n ≥ 3 .