Abstract Analysis of the reliability of networks is crucial to the design and optimization of networks. The $P$-conditional edge-connectivity $\lambda (P;G)$ of a network $G$ is the minimum number of edges whose deletion will divide $G$ into several components, and each component satisfies the property $P$. It proposes a more pinpoint analysis to the reliability of networks. The paper investigates several different the $P$-conditional edge-connectivities of $K_{p;t}^{n}$, such as $d$-embedded edge-connectivity $\lambda (P_{1}^{d};K_{p;t}^{n})$, $(t-1)pd$-good-neighbor edge-connectivity $\lambda (P_{3}^{(t-1)pd};K_{p;t}^{n})$, $(t-1)pd$-average edge-connectivity $\lambda (P_{4}^{(t-1)pd};K_{p;t}^{n})$ for $t\geq 2$, $p\geq 2$ and $0\leq d\leq n-1$, and they possess the same value $(t-1)p(n-d)(tp)^{d}$. Besides, we derive $\lambda (P_{2}^{l}; K_{p;t}^{n})= (t-1)pnl-ex_{l}(K_{p;t}^{n})$ for $1\leq l\leq (tp)^{{\lfloor \frac{n}{2} \rfloor }}$, where $ex_{l}(K_{p;t}^{n})$ denotes the twice of the maximum number of edges in a subgraph induced by $l$ vertices in $K_{p;t}^{n}$. Our method generalizes the result of Yu and Xu in (Comput J 2024; 67: 688–93) and Zhang et al. in (J Supercomput 2022; 78: 7936–47).

Reliability assessment of multiprocessor systems presents the theoretical foundation for the layout and optimization of multiprocessor systems. The$h$-extra edge-connectivity$\lambda _{h}$and the$k$-component edge-connectivity$c\lambda _{k}$, as extensions of the classical edge connectivity, are two precise metrics for the measurement of the reliability of multiprocessor systems. For multiprocessor systems, determining$c\lambda _{k}$and$\lambda _{k}$of a large$k$is still difficult. Let$\delta _{G}(0)=0$and$\delta _{G}(i)=\frac{1}{2}(\text{ex}_{i+1}(G)-\text{ex}_{i}(G))$for$i\in \lbrace 1, \ldots, |G|-1\rbrace$, where$\text{ex}_{i}(G)={\mathrm{max}}\lbrace 2|E(G[S])|: S\subseteq V(G), |S|=i \rbrace$. In this article, we obtain$c\lambda _{k}$and$\lambda _{h}$of the Cartesian powers of the$d$-regular graphs for which the lexicographic order yields an optimal order and$\delta _{G}(i)\leq \frac{d}{2}$for$i=0, 1, \ldots, \lfloor \frac{|G|-1}{2}\rfloor$. Our result improves some previous results about$c\lambda _{k}$of Hamming graphs by Yang et al. (2023), and$\lambda _{h}$of the Cartesian powers of the complete graph$K_{4}$by Tian et al. (2022).

Abstract Reliability evaluation of multiprocessor systems is of significant importance in the design and maintenance of multiprocessor systems. Based on edge-connectivity, more refined quantitative indicators for the reliability of multiprocessor systems have been introduced. The extra edge-connectivity and the component edge-connectivity, as two important parameters to evaluate the robustness of multiprocessor systems, are explored extensively. In this paper, we determine the $h$-extra edge-connectivity and the $(g+1)$-component edge-connectivity of the balanced complete $t$-partite graph $K_{r}^{t}$ for $t, r\geq 2$, where $1\leq h \leq \lfloor tr/2 \rfloor$ and $2\leq g \leq tr-1$.

Assessment on the reliability of interconnection networks plays a significance role in designing and maintaining interconnection networks. The conditional$h$-edge connectivity$\lambda ^{h}$, the$h$-average degree edge connectivity$\overline{\lambda ^{h}}$, and the$g$-extra edge connectivity$\lambda _{g}$are three considerable indicators for assessment of the reliability of interconnection networks, which can maximally improve the real fault tolerability of interconnection networks. In this article, we obtain the relationship between$\lambda ^{h}$(respectively,$\overline{\lambda ^{h}}$) and$\lambda _{g}$of graphs. Applying this newly established relationship, we obtain$\lambda ^{h}$(respectively,$\overline{\lambda ^{h}}$) of some famous interconnection networks, including 3-ary$n$-cubes, augmented cubes, and enhanced hypercubes. That is, we show that$\begin{aligned} \lambda ^{h}(\overline{\lambda ^{h}})(Q_{n}^{3})\!=\! \left\lbrace \begin{array}{@{}ll@{}}(2n-h)3^{\frac{h}{2}}, \ \ h\ \text{is even, } 0\leq h\leq 2n-2;\\ (4n \!-\! 2h)3^{\frac{h-1}{2}}, \ h\ \text{is odd, } 0\leq h\leq 2n \!-\! 3; \end{array} \right. \end{aligned}$when$k\ne 2$,$ \lambda ^{h}(\overline{\lambda ^{h}})(Q_{n,k})= \left\lbrace \begin{array}{@{}ll@{}}(n+1-h)2^{h}, \ 0\leq h\leq n-k;\\ (n+1-h)2^{h-1}, \ n\!-\!k \!+\! 2 \leq h\leq n; \end{array} \right. $when$k= 2$,$ \lambda ^{h}(\overline{\lambda ^{h}})(Q_{n,k})= \left\lbrace \begin{array}{@{}ll@{}}(n+1-h)2^{h}, \ 0\leq h\leq n-3;\\ 2^{n-1}, \ h= n-2, n-1; \end{array} \right. $and$\lambda ^{h}(AQ_{n})=\overline{\lambda ^{h}}(AQ_{n})=(n-\frac{h+1}{2})2^{\frac{h+3}{2}}$for$h$is odd within the range$1\leq h\leq 2n-3$. In particular, these results extend the previous results in [J. Supercomput.2022, 5: 6739-6751] and [Inform. Process. Lett.2008, 106: 59-63] and also solve positively a conjecture presented by Shinde and Borse [J. Interconnect. Netw.2020, 20: 2050013].

Abstract Reliability evaluation of interconnection networks is of significant importance to the design and maintenance of interconnection networks. The component connectivity is an important parameter for the reliability evaluation of interconnection networks and is a generalization of the traditional connectivity. The $g$-component connectivity $c\kappa _g (G)$ of a non-complete connected graph $G$ is the minimum number of vertices whose deletion results in a graph with at least $g$ components. Determining the $g$-component connectivity is still an unsolved problem in many interconnection networks. Let $Q_{n,k}$ ($1\leq k\leq n-1$) denote the $(n, k)$-enhanced hypercube. In this paper, let $n\geq 7$ and $1\leq k \leq n-5$, we determine $c\kappa _{g}(Q_{n,k}) = g(n + 1) - \frac{1}{2}g(g + 1) + 1$ for $2 \leq g \leq n$. The previous result in Zhao and Yang (2019, Conditional connectivity of folded hypercubes. Discret. Appl. Math., 257, 388–392) is extended.

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.

Reliability evaluation of multiprocessor systems is of great significance to the design and maintenance of these systems. As two generalizations of traditional edge connectivity, extra edge connectivity and component edge connectivity are two important parameters to evaluate the fault-tolerant capability of multiprocessor systems. Fast identifying the extra edge connectivity and the component edge connectivity of high order remains a scientific problem for many useful multiprocessor systems. In this article, we determine the$h$-extra edge connectivity of the 3-ary$n$-cube$Q_n^3$for$h\in [1, \frac{3^n-1}{2}]$. Specifically, we divide the interval$[1, \frac{3^n-1}{2}]$into some subintervals and characterize the monotonicity of$\lambda _h(Q_n^3)$in these subintervals and then deduce a recursive closed formula of$\lambda _h(Q_n^3)$. Based on this formula, an efficient algorithm with complexity$O(\log _3\,N)$is designed to determine the exact values of$h$-extra edge connectivity of the 3-ary$n$-cube$Q_n^3$for$h\in [1, \frac{3^n-1}{2}]$completely. Moreover, we also determine the$g$-component edge connectivity of the 3-ary$n$-cube$Q_n^3(n\geq 6$) for$1\leq g\leq 3^{\lceil \frac{n}{2}\rceil }$.

Abstract Let $G=(V(G), E(G))$ be a connected graph. A subset $T \subseteq V(G)$ is called an $R^{k}$-vertex-cut, if $G-T$ is disconnected and each vertex in $V(G)-T$ has at least $k$ neighbors in $G-T$. The cardinality of a minimum $R^{k}$-vertex-cut is the $R^{k}$-vertex-connectivity of $G$ and is denoted by $\kappa ^{k}(G)$. $R^{k}$-vertex-connectivity is a new measure to study the fault tolerance of network structures beyond connectivity. In this paper, we study $R^{1}$-vertex-connectivity and $R^{2}$-vertex-connectivity of Cayley graphs generated by wheel graphs, which are denoted by $AW_{n}$, and show that $\kappa ^{1}(AW_{n})=4n-7$ for $n\geq 6$; $\kappa ^{2}(AW_{n})=6n-12$ for $n\geq 6$.

For a connected graph G=(V(G),E(G))⁠, a subset F⊂V(G) is called an Rk-vertex-cut if G−F is disconnected and each vertex u∈V(G)−F has at least k neighbors in G−F⁠. The cardinality of a minimum Rk-vertex-cut of G is the Rk-vertex-connectivity and is denoted by κk(G)⁠. The conditional connectivity is a new measure to study the fault tolerance of network structures beyond connectivity. In this paper, we study R1-vertex-connectivity and R2-vertex-connectivity of Cayley graphs generated by 2-trees T2,n⁠, which are denoted by KTn⁠, and show that κ1(KTn)=4n−8 for n≥4⁠; κ2(KTn)=8n−22 for n≥6⁠.