The Component Diagnosability of Hypercubes with Large-Scale Faulty Nodes

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 ctg(G) and has not been addressed before. ctg(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 Qn\ (n≥ 7), ctg+1(Qn)=-(1/2)g2+(n-3/2)g+n when g\≤ n-1. Moreover, we determine the (n+1)-component diagnosability ctn+1(Qn)=n2/2+n/2-2 for n≥ 7.