Relationship Between Component Connectivity And Component Diagnosability Of Some Regular Networks

• Published in: Computer journal 2023-08, Vol.66 (8), p.2033-2042
• Main Authors: Sun, Xueli, Fan, Jianxi, Cheng, Baolei, Zhou, Jingya, Wang, Yan
• Format: Article
• Language: English
• ISSN: 0010-4620; 1460-2067
• DOI: 10.1093/comjnl/bxac061

Abstract 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.