Diagnosability of the Incomplete Star Graphs

The growing size of the multiprocessor systems increases their vulnerability to component failures. It is crucial to local and to replace the fault processors to maintain system’s high reliability. The fault diagnosis is the process of identifying faulty processors in a system through testing. This paper establishes the diagnosabilities of the incomplete star graph S_n (n≥4) with missing links under the PMC model and its variant, the BGM model, and shows that the diagnosabilities of incomplete star graph S_n under these two diagnostic models can be determined by the minimum degree of its topology structure. This method can also be applied to the other existing multiprocessor systems.