Conditional Diagnosability of Cayley Graphs Generated by Transposition Trees under the PMC Model

Processor fault diagnosis has played an essential role in measuring the reliability of a multiprocessor system. The diagnosability of many well-known multiprocessor systems has been widely investigated. Conditional diagnosability is a novel measure of diagnosability by adding a further condition that any fault set cannot contain all the neighbors of every node in the system. Several known structural properties of Cayley graphs are exhibited. Based on these properties, we investigate the conditional diagnosability of Cayley graphs generated by transposition trees under the PMC model and show that it is 4n-11 for n ≥ 4 except for the n -dimensional star graph for which it has been shown to be 8 n -21 for n ≥ 5 (refer to Chang and Hsieh [2014]).