The generalized 4-connectivity of folded hypercube

ABSTRACT

In recent years, a growing number of concepts have been proposed to better assess network fault tolerance, among which the generalized $k$-connectivity has been widely used in the research of fault tolerance of interconnection networks. For connected graph $G$, ${\kappa }_G(S)$ refers to the maximum number of internally disjoint trees in $G$ to connect $S$, where $S\subset V(G)$ with $|S|\ge 2$. The generalized $k$-connectivity of G ${\kappa }_k(G)=min\{{\kappa }_G(S)\mid S\subset V(G),|S|=k\}$. The $n$-dimensional folded hypercube $F{Q}_n$, as a hypercube-like network, is obtained by adding $2^{n-1}$ edges on $n$-dimensional hypercube $Q_n$. In this paper, we discuss the generalized 4-connectivity of $F{Q}_n$ and show that ${\kappa }_4(F{Q}_n)=n$ for $n\ge 7$.

KEYWORDS:

• Internally disjoint trees
• generalized k-connectivity
• hypercube
• folded hypercube
• fault-tolerance

Acknowledgments

The authors are very grateful to the anonymous reviewers for their valuable comments, which have provided great help to improve the quality of this paper.

Disclosure statement

The authors report there are no competing interests to declare(s).

Additional information

Funding

This article was completed during the period when the second author Dongqin Cheng was visiting Nanyang Technological University with financial support from China Scholarship Council (CSC) [grant number 202006785015].