The Reliability of k-Ary n-Cube Based on Component Connectivity

作者：Lv, Mengjie; Fan, Jianxi^*; Zhou, Jingya; Yu, Jia; Jia, Xiaohua

来源：COMPUTER JOURNAL, 2022, 65(8): 2197-2208.

DOI：10.1093/comjnl/bxab054

• k-ary n-cube
• reliability
• component connectivity
• component diagnosability
• PMC model
• MM* model

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(n)(k) n is c kappa(r+1)(Qn(k)) = 1/2 r(2) + ( n - 1/2)r + 1 for n >= 2, k >= 4 and 1 <= r <= n. In view of c kappa(r+1)(Q(n)(k)), we prove that the (r + 1)-component diagnosabilities of k-ary n-cube Q(n)(k) under the PMC model and MM* model are ct(r+1)(Q(n)(k)) = - 1/2r(2) + (2n - 3/2) r + 2n for n >= 4, k >= 4 and 1 <= r <= n - 1.

• 单位
  青岛大学; 苏州大学