The underlying topology of the interconnection network of parallel and distributed systems is usually modelled by a simple connected graph$G$. In order to quantitatively analyze the reliability and fault tolerance of these networks more accurately, this study introduces a novel topology parameter. The$g$-good$(r+1)$-component edge-connectivity$\lambda _{g,r+1}(G)$of$G$, if any, is the smallest cardinality of faulty link set, whose malfunction yields a disconnected graph with at least$r+1$connected components, and with the neighboring edges of any vertex being at least$g$. When designing and maintaining parallel and distributed systems, the hypercube network$Q_{n}$is one of the most attractive interconnection network models. This article offers a unified method to derive an upper bound for$g$-good$(r+1)$-component edge-connectivity$\lambda _{g,r+1}(Q_{n})$of$Q_{n}$. When$n\geq 4$, this upper bound is proved to be tight for$1\leq 2^{g}\cdot r\leq 2^{\lfloor \frac{n}{2}\rfloor }$or$r=2^{k_{0}}$,$0\leq k_{0}< \lfloor \frac{n}{2}\rfloor$,$0\leq g\leq n-2k_{0}-1$. The conclusions for the$g$-good-neighbor edge-connectivity of$Q_{n}$from Xu and the$(r+1)$-component edge-connectivity of$Q_{n}$from Zhao et al. are contained as corollaries of our main results for$r=1$,$0\leq g\leq n-1$and$1\leq r\leq 2^{\lfloor \frac{n}{2}\rfloor }$,$g=0$, respectively.

Abstract The conditional edge-connectivity is an important parameter to evaluate the reliability and fault tolerance of multi-processor systems. The $n$-dimensional bijective connection networks $B_{n}$ contain hypercubes, crossed cubes, Möbius cubes and twisted cubes, etc. The conditional edge-connectivity of a connected graph $G$ is the minimum cardinality of edge sets, whose deletion disconnects $G$ and results in each remaining component satisfying property $\mathscr{P}$. And let $F$ be the edge set as desired. For a positive integer $a$, if $\mathscr{P}$ denotes the property that the average degree of each component of $G-F$ is no less than $a$, then the conditional edge-connectivity can be called the $a$-average degree edge-connectivity $\overline{\lambda }_{a}(G)$. In this paper, we determine that the exact value of the $a$-average degree edge-connectivity of an $n$-dimensional bijective connection network $\overline{\lambda }_{a}(B_{n})$ is $(n-a)2^a$ for each $0\leq a \leq n-1 $ and $n\geq 1$. 1

Reliability analysis of an interconnection network is of great significance to the design and maintenance of multiprocessor systems. The h-extra edge-connectivity of a given interconnected network G with N processors, denoted by λh(G), is the minimum cardinality of set of faulty links, such that whose removal will disconnect the network with all its resulting components having at least h processors for h ≤ N/2. It gives a more refined quantitative analysis of indicators of the robustness of a multiprocessor system in the presence of failing links. The n-dimensional folded hypercube FQn, as one of potential interconnected networks, is a well-known variation of the hypercube structure with N = 2nprocessors. In this paper, the h-extra edge-connectivity of the network FQn, λh(FQn), is first investigated for each well-defined positive integer h ≤ N/2. We divide the interval 1 ≤ h ≤ N/2 into some subintervals and obtain some properties of λh(FQn) in these subintervals. Then, we deduce a recursive relation of λh(F Qn). Based on this recursion, an efficient O(log2(N)) algorithm is designed to totally determine the exact values and λh-optimality of λh(FQn) for each h ≤ N/2.