Component connectivity of Cayley graphs generated by transposition trees

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{\kappa }_r\left(G\right)$ of G is the size of the smallest r-component cut. The r-component edge connectivity $c{\lambda }_r\left(G\right)$ can be defined similarly. In this paper, we determine the r-component connectivity of Cayley graphs generated by transposition trees $c{\kappa }_{r+1}\left({\mathcal{T}}_n\right)=r(n-1)-r(r+1)/2+1$ for $r=1,2,\dots ,n-1$ and $n\ge 3$; we also obtain the r-component edge connectivity of Cayley graphs generated by transposition trees ${\mathcal{T}}_n$ for small r and the upper and lower bounds of $c{\lambda }_{r+1}\left({\mathcal{T}}_n\right)$ for $r=1,2,\dots ,n-1$ and $n\ge 3$.

KEYWORDS:

• Interconnection network
• component connectivity
• component edge connectivity
• Cayley graph
• fault tolerance

Acknowledgments

The authors are grateful to the editor and the anonymous referees for many helpful comments and suggestions.

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This work is supported by National Natural Science Foundation of China (Nos.11301217, 61572010, 11571139), New Century Excellent Talents in Fujian Province University (No. JA14168) and Natural Science Foundation of Fujian Province, China (Nos. 2018J01419, 2017J01738).