The g-good-neighbor diagnosability of triangle-free graphs

Today's supercomputers contain thousands of processing cores. As the number of processing units grows, the probability of failing some processing units increases. Therefore, finding faulty units has become a concern in these systems which depends on the diagnosability of the interconnection network that connects processing units. In this paper, we investigate the g-good-neighbor diagnosability of triangle-free graphs under the MM* and PMC models. We show that if G is a connected triangle-free graph with minimum degree delta, its diagnosability under the MM* model, i.e., t(MM)* (G), is either delta - 2, delta - 1, or delta. Also, the 1-good-neighbor diagnosability of G, i.e., t(1)(MM)* (G), is at least delta - 1 if it does not contain any subgraph isomor- phic to K-delta,K-delta. Moreover, we show that if G does not contain a subgraph isomorphic to K delta-1, (delta)(-1), then it is 1-good-neighbor (delta + 1)-diagnosable under PMC model when vertical bar V(G)vertical bar > 2 delta + 2. Our results give lower bounds on the diagnosability and 1-goodneighbor diagnosability of triangle-free graphs which covers a broad class of interconnection networks.

Automated summary

This paper investigates the diagnosability of interconnection networks in supercomputers and provides some conclusions based on the analysis of triangle-free graphs.