Structural diagnosability of hypercubes under the PMC and MM* models.

The fault diagnosability has played an important role in the reliability of the interconnection network. In a network, the states of any two adjacent vertices can usually affect each other, and the neighbor of a faulty vertex is more likely to become faulty. These motivate our study of fault diagnosability from the perspective of some structures instead of basing on individual faulty vertices. Therefore, we introduce a novel measure of diagnosability, called structural diagnosability. Given a specific structure H , the H -structure diagnosability of a network G , denoted by t s (G ; H) , is the maximum number of pairwise disjoint subnetworks H 1 , H 2 , ... , H m in G , such that, for i = 1 , 2 , ... , m , H i is isomorphic to H and when all vertices in H i are faulty, these vertices can be diagnosed correctly. In this paper, we will establish t s (Q n ; H) for the n -dimensional hypercube Q n under the PMC model and MM* model, respectively, where H ∈ { K 1 , 1 , K 1 , 2 , K 1 , 3 , C 4 }. [ABSTRACT FROM AUTHOR]