Characterization of Cyclic Diagnosability of Regular Diagnosable Networks

The reliability of interconnection network ordinarily is measured by two significant indexes, namely, connectivity and diagnosability. The qualitative and quantitative reliability analysis relies on the choice of an appropriate mathematical modeling and assumptions consistent with the actual situation. The cyclic connectivity is a well-established index to evaluate the reliability of interconnection network. For a networkG, we use kc(G) to denote cyclic connectivity of G, which is the minimum size of the node cut setDsuch thatG - Dis disconnected and at least two of its components have cycles. Based on the cyclic connectivity, cyclic diagnosability (ct(G)) is proposed to measure the self-diagnostic capability of the networks. Up to this day, the cyclic connectivity of some special networks has been determined successfully, but the cyclic diagnosability of a great deal of networks is still up in the air. In this work, we investigate the measurable relationship between cyclic connectivity and 2-good connectivity under certain restrictions. Furthermore, we characterize the cyclic diagnosability of a class of networks in terms of character commonality of the networks. To be more specific, we show that ct(G) = kc(G) + (l - k) under the PMC model (PMC-M) and the MM∗ model (MM∗-M), where l is the regular degree of network and l ≥ 3, 1 ≤ k < l are constant. Then, we directly determine the cyclic diagnosability of hypercubes, locally twisted cubes, and alternating group networks. Finally, we compare the cyclic diagnosability of the network with other kinds of restricted diagnosabilities. The results show that cyclic diagnosability has excellent self-diagnostic capability.