-
Views
-
Cite
Cite
Shanshan Yin, Liqiong Xu, On the g-Extra Connectivity of the Enhanced Hypercubes, The Computer Journal, Volume 65, Issue 9, September 2022, Pages 2339–2346, https://doi.org/10.1093/comjnl/bxab069
- Share Icon Share
Abstract
Reliability evaluation of interconnection networks is of significant importance to the design and maintenance of interconnection networks. The extra connectivity is an important parameter for the reliability evaluation of interconnection networks and is a generalization of the traditional connectivity. Let |$g\geq 0$| be an integer and |$G$| be a connected graph; the |$g$|-extra connectivity of |$G$| is the minimum cardinality of a set of vertices in |$G$|, if it exists, whose removal disconnects |$G$| and leaves every component with more than |$g$| vertices. Determining the |$g$|-extra connectivity is still an unsolved problem in many interconnection networks. Let |$n$|, |$k$| be positive integers. Let |$Q_{n,k}\, (1 \leq k \leq n-1)$| denote the |$(n, k)$|-enhanced hypercube. In this paper, we determine the |$g$|-extra connectivity of |$Q_{n,k}$| is |$(n+1)(g+1)-\frac{g(g+3)}{2}$| for |$0\leq g\leq n-k-1$|, |$4\leq k\leq n-5\,(n\geq 9)$|. Some previous results in [Zhang, M. and Zhou, J. (2015) On g-extra connectivity of folded hypercubes. Theor. Comput. Sci., 593, 146–153.] and [Sabir, E., Mamut, A. and Vumar, E. (2019) The extra connectivity of the enhanced hypercubes. Theor. Comput. Sci., 799, 22–31.] are extended.