The g-good-neighbor conditional diagnosability of star graphs under the PMC and MM* model

Diagnosability plays an important role in measuring the fault tolerance and reliability of interconnection networks. The g-good-neighbor conditional faulty set is a special faulty set that every fault-free vertex should have at least g fault-free neighbors. The g-good neighbor conditional diagnosability is a metric that can give the maximum cardinality of g-good-neighbor conditional faulty set that the system is guaranteed to identify. This paper shows that the g-good-neighbor conditional diagnosabilities of star graph S-n, under the PMC and MM* model are (n - g)(g + 1)1 - 1 for n >= 4 and 0 <= g <= n - 2. Our study shows the g-good-neighbor conditional diagnosability of star graph is several times larger than the classical diagnosability of star graph. (C) 2017 Elsevier B.V. All rights reserved.