Diagnosable evaluation of DCC linear congruential graphs under the PMC diagnostic model

A DCC (disjoint consecutive cycles) linear congruential graph G(F, n) consists of n nodes and is generated by a set of linear functions F with special properties. It was proved that G(F, n) is a 2t-regular graph and has connectivity 2t  , where t=|F|t=|F| and 1⩽t⩽p-11⩽t⩽p-1 (n=2pn=2p for some integer p  ). For a multiprocessor system, its diagnosability is critical to measure the performance. In this paper, we study the diagnosability of G(F,2p)G(F,2p) under the precise and pessimistic diagnosis strategies based on the PMC (Preparata, Metze, and Chien) diagnostic model. It is proved that G(F,2p)G(F,2p) is 2t  -diagnosable and (4t-5)/(4t-5)(4t-5)/(4t-5)-diagnosable under the two diagnosis strategies, respectively, where p⩾3p⩾3 and 2⩽t⩽p-12⩽t⩽p-1. In addition, the diagnosability of DCC linear congruential graphs is compared with that of BC (bijective connection) graphs.