Search

As a kind of conditional connectivity, component connectivity is an improvement of traditional connectivity, which is conducive to enhance the reliability of the network. To be specific, the |$r$| -component connectivity of a network |$G$|⁠ , written as |$c\kappa _{r}(G)$|⁠ , is defined as the minimum number of all node cuts whose removal causes the remaining network to have at least |$r$| components. Component diagnosability, as another measure of network reliability, is usually related to the number of components in the remaining network. The |$r$| -component diagnosability, written as |$ct_{r}(G)$|⁠ , is defined as the maximum number of faulty sets such that at least |$r$| components in the surviving network and all faulty nodes can be diagnosed. This paper mainly explores the relationship between component connectivity and component diagnosability of some regular networks. Once knowing the component connectivity of such a network, with the help of this relationship, we can easily obtain the component diagnosability of the network. Furthermore, we apply this relationship to some famous regular networks to obtain their component diagnosabilities under the PMC model. [ABSTRACT FROM AUTHOR]

Connectivity and diagnosability are two crucial subjects for a network's ability to tolerate and diagnose faulty processors. The |$r$| -component connectivity |$c\kappa _{r}(G)$| of a network |$G$| is the minimum number of vertices whose deletion results in a graph with at least |$r$| components. The |$r$| -component diagnosability |$ct_{r}(G)$| of a network |$G$| is the maximum number of faulty vertices that the system can guarantee to identify under the condition that there exist at least |$r$| fault-free components. This paper first establishes that the |$(r+1)$| -component connectivity of |$k$| -ary |$n$| -cube |$Q^{k}_{n}$| is |$c\kappa _{r+1}(Q^{k}_{n})=-\frac{1}{2}r^{2}+\Big(2n-\frac{1}{2}\Big)r+1$| for |$n\geq 2$|⁠ , |$k\geq 4$| and |$1\leq r\leq n$|⁠. In view of |$c\kappa _{r+1}(Q^{k}_{n})$|⁠ , we prove that the |$(r+1)$| -component diagnosabilities of |$k$| -ary |$n$| -cube |$Q^{k}_{n}$| under the PMC model and MM* model are |$ct_{r+1}(Q^{k}_{n})=-\frac{1}{2}r^{2}+\Big(2n-\frac{3}{2}\Big)r+2n$| for |$n\geq 4$|⁠ , |$k\geq 4$| and |$1\leq r\leq n-1$|⁠. [ABSTRACT FROM AUTHOR]

As the number of servers in a data center network (DCN) increases, the probability of server failures is significantly increased. Traditional connectivity is an important metric to measure the reliability of DCN. However, the traditional connectivity of a DCN based on the condition of arbitrary faulty servers is generally lower. Therefore, it is important to increase the connectivity of a DCN by adding some limited conditions for the faulty server set. As a result, |$g$| -restricted connectivity and |$h$| -extra connectivity, which are two crucial subjects for a DCN's ability to tolerate faulty servers, were proposed in the literature. In this paper, we study the |$g$| -restricted connectivity and |$h$| -extra connectivity of a new server-centric DCN, called BCDC, based on crossed cube with excellent performance. We prove that the |$g$| -restricted connectivity of BCDC is 4 for |$n=3$| and |$2n+g(n-2)-2$| for |$n\geq 4$|⁠ , where |$0\leq g\leq n-3$|⁠ , and the |$h$| -extra connectivity of BCDC is 4 for |$n=3$| and |$2n+h(n-2)-2$| for |$n\geq 4$|⁠ , where |$0\leq h\leq n-3$|⁠. [ABSTRACT FROM AUTHOR]

Connectivity is a classic measure for reliability of a multiprocessor system in the case of processor failures. Extra connectivity and component connectivity are two important indicators of the reliability of a multiprocessor system in presence of failing processors. The |$h$| -extra connectivity |$\kappa _{h}(G)$| of a graph |$G$| is the minimum number of nodes whose removal will disconnect |$G$|⁠ , and every remaining component has at least |$h+1$| nodes. Moreover, the |$h$| -component connectivity |$c\kappa _{h}(G)$| of |$G$| is the minimum number of nodes whose deletion results in a graph with at least |$h$| components. However, the extra connectivity and component connectivity of many well-known networks have been independently investigated. In this paper, we determine the relationship between extra connectivity and component connectivity of general networks. As applications, the extra connectivity and component connectivity are explored for some well-known networks, including complete cubic networks, hierarchical cubic networks, generalized exchanged hypercubes, dual-cube-like networks, Cayley graphs generated by transposition trees and hierarchical hypercubes as well. [ABSTRACT FROM AUTHOR]