The Reliability of k-Ary n-Cube Based on Component Connectivity. (20th May 2021)

• Record Type: Journal Article
• Authors: Lv, Mengjie; Fan, Jianxi; Zhou, Jingya; Yu, Jia; Jia, Xiaohua
• Editors: Stewart, Iain
• Is Part Of: Computer journal. Volume 65:Number 8(2022)
• Page Start: 2197
• Page End: 2208
• Publication Date: 2021-05-20
• Subjects: k-ary n-cube -- reliability -- component connectivity -- component diagnosability -- PMC model -- MM* model; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxab054
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: 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^{k}_{n}$ is $c\kappa _{r+1}(Q^{k}_{n})=-\frac{1}{2}r^{2}+\Big(2n-\frac{1}{2}\Big)r+1$ for $n\geq 2$, $k\geq 4$ and $1\leq r\leq n$ . In view of $c\kappa _{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\geq 4$, $k\geq 4$ and $1\leq r\leq n-1$ .