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 …
Abstract
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 and models. We show that if G is a connected triangle-free graph with minimum degree , its diagnosability under the model, i.e., , is either , , or . Also, the 1-good-neighbor diagnosability of G, i.e., , is at least if it does not contain any subgraph isomorphic to . Moreover, we show that if G does not contain a subgraph isomorphic to then it is 1-good-neighbor \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\left( {\delta + 1} \right)$$\end{document}-diagnosable under model when . Our results give lower bounds on the diagnosability and 1-good-neighbor diagnosability of triangle-free graphs which covers a broad class of interconnection networks.