The Reliability of k-Ary n-Cube Based on Component Connectivity. (20th May 2021) - Lv, Mengjie; Fan, Jianxi; Zhou, Jingya; Yu, Jia; Jia, Xiaohua
Abstract: Connectivity and diagnosability are two crucial subjects for a network's ability to tolerate and diagnose faulty processors. The r -component connectivity cκ _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κ _r+1(Q^k_n)=-12r^2+(2n-12)r+1 for n≥ 2, k≥ 4 and 1≤ r≤ n . In view of cκ _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)=-12r^2+(2n-32)r+2n for n≥ 4, k≥ 4 and 1≤ r≤ n-1 .