Characterization of Cyclic Diagnosability of Regular Diagnosable Networks

Hong Zhang, Shuming Zhou, Eddie Cheng, Sun Yuan Hsieh

Research output: Contribution to journalArticlepeer-review


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 network <inline-formula><tex-math notation="LaTeX">$\TBmathbbsf {G}$</tex-math></inline-formula>, we use <inline-formula><tex-math notation="LaTeX">$\kappa _{c}(\TBmathbbsf {G})$</tex-math></inline-formula> to denote cyclic connectivity of <inline-formula><tex-math notation="LaTeX">$\TBmathbbsf {G}$</tex-math></inline-formula>, which is the minimum size of the node cut set <inline-formula><tex-math notation="LaTeX">$D$</tex-math></inline-formula> such that <inline-formula><tex-math notation="LaTeX">$\TBmathbbsf {G}-D$</tex-math></inline-formula> is disconnected and at least two of its components have cycles. Based on the cyclic connectivity, cyclic diagnosability (<inline-formula><tex-math notation="LaTeX">$ct(\TBmathbbsf {G})$</tex-math></inline-formula>) 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 <inline-formula><tex-math notation="LaTeX">$ct(\TBmathbbsf {G})=\kappa _{c}(\TBmathbbsf {G})+(l-k)$</tex-math></inline-formula> under the PMC model (PMC-M) and the MM<inline-formula><tex-math notation="LaTeX">$^\ast$</tex-math></inline-formula> model (MM<inline-formula><tex-math notation="LaTeX">$^\ast$</tex-math></inline-formula>-M), where <inline-formula><tex-math notation="LaTeX">$l$</tex-math></inline-formula> is the regular degree of network and <inline-formula><tex-math notation="LaTeX">$l\geq 3, 1\leq k&lt; l$</tex-math></inline-formula> 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.

Original languageEnglish
Pages (from-to)1-9
Number of pages9
JournalIEEE Transactions on Reliability
Publication statusAccepted/In press - 2023

All Science Journal Classification (ASJC) codes

  • Safety, Risk, Reliability and Quality
  • Electrical and Electronic Engineering


Dive into the research topics of 'Characterization of Cyclic Diagnosability of Regular Diagnosable Networks'. Together they form a unique fingerprint.

Cite this