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

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) = −1/2r² + (2n − 1/2)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) = −1/2r² + (2n − 3/2)r + 2n for n ≥ 4, k ≥ 4 and 1 ≤ r ≤ n − 1.