Relating the extra connectivity and the conditional diagnosability of regular graphs under the comparison model

• We propose the fault tolerant properties of regular graphs with some basic conditions.
• The conditional diagnosability under the comparison model is equal to the 2-extra connectivity.
• The 2-extra connectivity of Sn is 3n−73n−7 by our proposed relationship.
• The 2-extra connectivity of Cayley graphs generated by transposition trees is 3n−83n−8.

Extra connectivity and conditional diagnosability are two crucial subjects for a multiprocessor system's ability to tolerate and diagnose faulty processors. The extra connectivity and the conditional diagnosability of many well-known multiprocessor systems have been widely investigated. In this paper, the relationship between the extra connectivity and the conditional diagnosability of regular graphs is explored. We establish that the conditional diagnosability under the comparison model is equal to the 2-extra connectivity. Finally, we give empirical analysis on the extra connectivity and conditional diagnosability of some graphs by our proposed relationship.