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 g -component diagnosability of network G, which is denoted by ct_g(G) and has not been addressed before. ct_g(G) is the maximum number of nodes in the faulty node set F of G such that G-F has at least g components and diagnosis model can identify all nodes in F . Under PMC and MM^* diagnosis models, we show that, in the hypercube Q_n (n≥ 7), ct_g+1(Q_n)=-(1/2)g^2+(n-3/2)g+n when g≤ n-1 . Moreover, we determine the (n+1) -component diagnosability ct_n+1(Q_n)=n^2/2+n/2-2 for n≥ 7 .