Intermittent Fault Diagnosability of Some General Regular Networks

摘要

Fault tolerance plays an important role in the interconnection networks, where permanent and intermittent faults are two kinds of fault situations. Permanent fault diagnosabilities of regular networks have been proposed widely while the intermittent fault diagnosabilities are also noteworthy. In this paper, we give a sufficient and necessary condition for k-regular k-connected graph Gn to be ti-diagnosable without repair in intermittent fault pattern. Detailly, we show that the intermittent fault diagnosability of Gn under the PMC model is $k-lceilrac{g-1}{2} ceil-2$, where g is the maximum number of common neighbors for any two distinct vertices. As applications, intermittent fault diagnosabilities of many famous networks are explored.