The Reliability ofk-Aryn-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κ ᵣ(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ᵣ(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ᵏₙ is cκ ᵣ₊₁(Qᵏₙ)=-1/2r²+(2n-1/2)r+1 for n≥ 2, k≥ 4 and 1≤ r≤ n. In view of cκ ᵣ₊₁(Qᵏₙ), we prove that the $(r+1)$-component diagnosabilities of k-ary n-cube Qᵏₙ under the PMC model and MM* model are ctᵣ₊₁(Qᵏₙ)=-1/2r²+(2n-3/2)r+2n for n≥ 4, k≥ 4 and 1≤ r≤ n-1.