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})=-\frac{1}{2}r^{2}+\Big(2n-\frac{1}{2}\Big)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})=-\frac{1}{2}r^{2}+\Big(2n-\frac{3}{2}\Big)r+2n$ for $n≥ 4$, $k≥ 4$ and $1≤ r≤ n-1$ .