The non-inclusive g-good-neighbor diagnosability of interconnection networks

Motivated by the definitions of g-good-neighbor diagnosability and non-inclusive diagnosability, we propose a new diagnosability-the non-inclusive g-good-neighbor diagnosability t(Ng)(G) of a multiprocessor system G, which requires every pair of g-good-neighbor faulty sets is non-inclusive. The R-g-conditional diagnosability t(Rg)(G) of a system G is a generalization of conditional diagnosability, which requires at least g fault-free neighbors for each node. In this paper, we explore the relationships between the non-inclusive g-good-neighbor diagnosability and the R-g-conditional diagnosability of G under the PMC and MM* models. We first show t(Ng)(G) <= t(Rg)(G) for g >= 1, and also give some conditions for equality. Next, we discuss the non-inclusive g-good-neighbor diagnosability of hypercubes, (n, k)-star graphs and (n, k)-bubble-sort graphs. We show that the non-inclusive g-good-neighbor diagnosability of n-dimensional hypercubes is less that its R-g-conditional diagnosability for 2 <= g <= n-2/2, and determine the non-inclusive g-good-neighbor diagnosability of (n, k)-star graphs and (n, k)-bubble-sort graphs. Finally, we plot and compare the non-inclusive g-good-neighbor diagnosability and the g-good-neighbor diagnosability of (n, k)-star graphs and (n, k)-bubble-sort graphs under the PMC and MM* models, respectively. It can be seen that their non-inclusive g-good-neighbor diagnosability is significantly larger than their g-good-neighbor diagnosability. (C) 2022 Elsevier B.V. All rights reserved.

Automated summary

This paper introduces the definitions of non-inclusive g-good-neighbor diagnosability t(Ng)(G) and R-g-conditional diagnosability t(Rg)(G), and explores their relationships under different network structures. The research findings show that, under certain conditions, the non-inclusive g-good-neighbor diagnosability is less than the R-g-conditional diagnosability.