On conditional diagnosability of the folded hypercubes

The n-dimensional folded hypercube FQn, a variation of the hypercube proposed by Ahmed et al. [A. El-Amawy, S. Latifi, Properties and performance of folded hypercubes, IEEE Transactions on Parallel and Distributed Systems 2(3) (1991) 31–42], is an (n + 1)-regular (n + 1)-connected graph. Conditional diagnosability, a new measure of diagnosability introduced by Lai et al. [Pao-Lien Lai, Jimmy J.M. Tan, Chien-Ping Chuang, Lih-Hsing Hsu, Conditional diagnosability measures for large multiprocessor systems, IEEE Transactions on Computers 54(2) (2005) 165–175] can better measure the diagnosability of regular interconnection networks. This paper determines that under PMC-model the conditional diagnosability of FQn (tc(FQn)) is 4n − 3 when n = 5 or n ⩾ 8; tc(FQ3) = 3, tc(FQ4) = 7.