The reliability of interconnection network ordinarily is measured by two significant indexes, namely, connectivity and diagnosability. The qualitative and quantitative reliability analysis relies on the choice of an appropriate mathematical modeling and assumptions consistent with the actual situation. The cyclic connectivity is a well-established index to evaluate the reliability of interconnection network. For a network $\TBmathbbsf {G}$ , we use $\kappa _{c}(\TBmathbbsf {G})$ to denote cyclic connectivity of $\TBmathbbsf {G}$ , which is the minimum size of the node cut set $D$ such that $\TBmathbbsf {G}-D$ is disconnected and at least two of its components have cycles. Based on the cyclic connectivity, cyclic diagnosability ( $ct(\TBmathbbsf {G})$ ) is proposed to measure the self-diagnostic capability of the networks. Up to this day, the cyclic connectivity of some special networks has been determined successfully, but the cyclic diagnosability of a great deal of networks is still up in the air. In this work, we investigate the measurable relationship between cyclic connectivity and 2-good connectivity under certain restrictions. Furthermore, we characterize the cyclic diagnosability of a class of networks in terms of character commonality of the networks. To be more specific, we show that $ct(\TBmathbbsf {G})=\kappa _{c}(\TBmathbbsf {G})+(l-k)$ under the PMC model (PMC-M) and the MM $^\ast$ model (MM $^\ast$ -M), where $l$ is the regular degree of network and $l\geq 3, 1\leq k< l$ are constant. Then, we directly determine the cyclic diagnosability of hypercubes, locally twisted cubes, and alternating group networks. Finally, we compare the cyclic diagnosability of the network with other kinds of restricted diagnosabilities. The results show that cyclic diagnosability has excellent self-diagnostic capability.

Motivated by a multitude of practical applications, many distinct vulnerability parameters of multiprocessor systems have been explored. Traditional connectivity and diagnosability are undoubtedly the most well investigated of these metrics, but often fail to capture the most subtle differences of a multiprocessor system. Subsequently, it is necessary to take into account the minimum degree of components, the size of components or the number of components. However, the structure of the components is ignored in these circumstances. In this work, we propose a novel diagnostic strategy based on cyclic connectivity, namely the cyclic diagnosability. The cyclic diagnosability, denoted by |$ct(G)$|⁠, is the maximum size of the faulty vertex set |$F$| of |$G$| such that the self-diagnosable system |$G$| can identify all the vertices in |$F$| under the condition that at least two connected components of |$G-F$| contain a cycle. Furthermore, we investigate the cyclic diagnosability of hypercube |$Q_{n}$| under the PMC model and the MM^* model, and show that |$ct(Q_{n})=5n-10$| for |$n\geq 7$|⁠.

As a critical parameter in evaluating the reliability of a multiprocessor system when processors malfunction, the \boldmath $h$ -extra connectivity ( $h$ -EC) of a multiprocessor system modeled by a graph $G$ , denoted by $\kappa ^{(h)}_{o}(G)$ , is an $h$ -extra vertex-cut with minimum cardinality. Both of the $h$ -extra conditional diagnosability ( $h$ -ECD) and the $t/h$ -diagnosability of the multiprocessor system are vital to tolerate and diagnose faulty processors. These two parameters rely on the resolving of $h$ -EC. For the multiprocessor system based on star graph $S_{n}$ , we show that the 5-EC $\kappa ^{(5)}_{o}(S_{n})$ of $S_{n}$ ( $n\geq 5$ ) is $6n-18$ . As a by-product, we present a novel proof of $\kappa ^{(2)}_{o}(S_{n})=3n-7$ (resp., $\kappa ^{(4)}_{o}(S_{n})=5n-14$ ) by relaxing the restriction $n\geq 10$ (resp., $n\geq 7$ ) to $n\geq 5$ (resp., $n\geq 5$ ). Furthermore, we determine that the $h$ -ECD of $S_{n}$ $(n\geq 5)$ under the preparata, metze, and chien (PMC) model is $(h+1)n-2h-1$ for $1\leq h\leq 3$ and $(h+1)n-3h+2$ for $4\leq h\leq 5$ . In addition, we show that $S_{n}$ is $[(h+1)n-4h+2]/h$ -diagnosable for $4\leq h\leq 5$ , which extends the result that $S_{n}$ is $[(h+1)n-3h-1]/h$ -diagnosable for $1\leq h\leq 3$ by [Zhou et al. “The t/k-diagnosability of star graph networks,” IEEE Trans. Comput., vol. 64, no. 2, pp. 547–555, Feb. 2015].

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 }$ .