Conditional diagnosability of multiprocessor systems based on complete-transposition graphs

Diagnosability is an important parameter to measure the ability of diagnosing faulty processors of a multiprocessor system. Conditional diagnosability is a realistic improvement of classical diagnosability under the condition that every processor has at least one fault free neighboring processor. Complete-transposition graphs are proposed to be potential competitive network models of hypercubes as well as star graphs. In this paper, we show that the conditional diagnosability of the complete-transposition graph CTn under the MM* model is 3/2 n(n - 1) 6 for n >= 7, while the conditional diagnosability of CTn under the PMC model is 2n(n - 1) 9 for n >= 5. (C) 2018 Elsevier B.V. All rights reserved.