The conditional fault diagnosability of (n, k)-star graphs

摘要

The growing size of the multiprocessor system increases its vulnerability to component failures. It is crucial to locate and replace the faulty processors to maintain a system’s high reliability. The fault diagnosis is the process of identifying faulty processors in a system through testing. This paper shows that the largest connected component of the survival graph contains almost all the remaining vertices when a lot of faulty vertices occur in the (n, k)-star graph Sn,k(n⩾5,k⩾3,n-k⩾2). Based on this fault resiliency, it establishes the conditional fault diagnosability of Sn,k under the comparison model.