TY - JOUR
T1 - Relationship Between Extra Connectivity and Component Connectivity In Networks
AU - LI, Xiaoyan
AU - LIN, Cheng-Kuan
AU - FAN, Jianxi
AU - JIA, Xiaohua
AU - CHENG, Baolei
AU - ZHOU, Jingya
PY - 2021/1
Y1 - 2021/1
N2 - 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 κ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κ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.
AB - 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 κ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κ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.
KW - component connectivity
KW - extra connectivity
KW - irregular networks
KW - regular networks
KW - reliability
UR - http://www.scopus.com/inward/record.url?scp=85104779634&partnerID=8YFLogxK
UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85104779634&origin=recordpage
U2 - 10.1093/comjnl/bxz136
DO - 10.1093/comjnl/bxz136
M3 - RGC 21 - Publication in refereed journal
VL - 64
SP - 38
EP - 53
JO - Computer Journal
JF - Computer Journal
SN - 0010-4620
IS - 1
ER -