We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
The g-good-neighbor diagnosability of triangle-free graphs.
- Authors
Sardroud, Asghar A. Asgharian; Ghasemi, Mohsen
- 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 MM ∗ and PMC models. We show that if G is a connected triangle-free graph with minimum degree δ , its diagnosability under the MM ∗ model, i.e., t MM ∗ (G) , is either δ - 2 , δ - 1 , or δ . Also, the 1-good-neighbor diagnosability of G, i.e., t 1 MM ∗ (G) , is at least δ - 1 if it does not contain any subgraph isomorphic to K δ , δ . Moreover, we show that if G does not contain a subgraph isomorphic to K δ - 1 , δ - 1 , then it is 1-good-neighbor δ + 1 -diagnosable under PMC model when | V (G) | > 2 δ + 2 . 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.
- Subjects
GRAPH connectivity; SUPERCOMPUTERS; TRIANGLES; MULTIPROCESSORS
- Publication
Journal of Supercomputing, 2023, Vol 79, Issue 7, p7272
- ISSN
0920-8542
- Publication type
Article
- DOI
10.1007/s11227-022-04942-1