The Component Diagnosability of Hypercubes with Large-Scale Faulty Nodes. (14th December 2020) - Zhang, Shurong; Liang, Dongyue; Chen, Lin; Li, Ronghua; Yang, Weihua
Abstract: The diagnosability is one of the most important measures of the reliability of networks. Consider the setting where there are large-scale failures that disconnect the network and result in many components. Then, the diagnosability is closely related to the number of components. In this paper, we define and study the $\boldsymbol{g}$ -component diagnosability of network $\boldsymbol{G}$, which is denoted by $\boldsymbol{ct_g(G)}$ and has not been addressed before. $\boldsymbol{ct_g(G)}$ is the maximum number of nodes in the faulty node set $\boldsymbol{F}$ of $\boldsymbol{G}$ such that $\boldsymbol{G-F}$ has at least $\boldsymbol{g}$ components and diagnosis model can identify all nodes in $\boldsymbol{F}$ . Under PMC and MM$^*$ diagnosis models, we show that, in the hypercube $\boldsymbol{Q_n\ (n≥ 7)}$, $\boldsymbol{ct_{g+1}(Q_n)=-(1/2)g^2+(n-3/2)g+n}$ when $\boldsymbol{g≤ n-1}$ . Moreover, we determine the $\boldsymbol{(n+1)}$ -component diagnosability $\boldsymbol{ct_{n+1}(Q_n)=n^2/2+n/2-2}$ for $\boldsymbol{n≥ 7}$ .