An interconnection network’s diagnosability is an important measure of its self-diagnostic capability. Based on the classical notion of diagnosability, strong diagnosability and conditional diagnosability were proposed later to better reflect the networks’ self-diagnostic capability under more realistic assumptions. In this paper, we study a class of interconnection networks called strong networks, which are$n$-regular,$(n - 1)$-connected, and with$cn$-number no more than$n - 3$. We build a relationship among the three diagnosability measures for strong networks. Under both PMC and${\rm MM}^{\ast}$models, given a strong network$G$with diagnosability$t$, we prove that$G$is strongly$t$-diagnosable if and only if$G$’s conditional diagnosability is greater than$t$. A simple check can show that almost all well-known regular interconnection networks are strong networks. The significance of this paper’s result is that it reveals an important relationship between strong and conditional diagnosabilities, and the proof of strong diagnosability for many interconnection networks under${\rm MM}^{\ast}$or PMC model is not necessary if their conditional diagnosability can be shown to be strictly larger than their diagnosability.

Reliability evaluation of interconnection network is important to the design and maintenance of multiprocessor systems. Extra connectivity determination and faulty networks' structure analysis are two important aspects for the reliability evaluation of interconnection networks. An n-dimensional bijective connection network (in brief, BC network), denoted by Xn, is an n-regular graph with 2nvertices and n2n-1edges. The hypercubes, Mobius cubes, crossed cubes, and twisted cubes are some examples of the BC networks. By exploring the boundary problem of the BC networks, we prove that when n ≥ 4 and 0 ≤ h ≤ n - 4 the h-extra connectivity of an n-dimensional BC network Xnis kh(Xn= n(h + 1)- 1/2h (h + 3). Furthermore, there exists a large connected component and the remaining small components have at most h vertices in total if the total number of faulty vertices is strictly less its h-extra connectivity. As an application, the results on the h-extra connectivity and structure of faulty networks on hypercubes, Mobius cubes, crossed cubes, and twisted cubes are obtained.