The generalized 4-connectivity of complete-transposition graphs

Abstract

The fault tolerability of the network is usually measured by the classical or generalized connectivity of the graph. For any subset $S\subseteq V\left(G\right)$ with $\left|S\right|\ge 2$, a tree T is called an S-tree if $S\subseteq V\left(T\right)$. Furthermore, any two S-tree $T_1$ and $T_2$ are internally disjoint if $E\left(T_1\right)\cap E\left(T_2\right)=\mathrm{\varnothing }$ and $V\left(T_1\right)\cap V\left(T_2\right)=S$. We denote by ${\kappa }_G\left(S\right)$ the maximum number of pairwise internally disjoint S-trees in G. For an integer $k\ge 2$, the generalized k-connectivity of a graph G is defined as ${\kappa }_k\left(G\right)=min\{{\kappa }_G\left(S\right)|S\subseteq V\left(G\right)$ and $\left|S\right|=k\}$. In this paper, we establish the generalized 4-connectivity of the Cayley graph $C{T}_n$ generated by complete graphs.

Keywords:

• Fault tolerability
• generalized connectivity
• Cayley graphs
• complete graphs

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work was partly supported by the National Natural Science Foundation of China (Nos. 61977016, 61572010, and 62277010), Natural Science Foundation of Fujian Province, China (Nos. 2020J01164, 2017J01738). This work was also partly supported by China Scholarship Council (CSC No. 202108350054).