An Approach to Conditional Diagnosability Analysis under the PMC Model and its Application to Torus Networks

A general technique is proposed for determining the conditional diagnosability of interconnection networks under the PMC model. Several graph invariants are involved in the approach, such as the length of the shortest cycle, the minimum number of neighbors, γp (resp. γ′p), over all p-vertex subsets (resp. cycles), and a variant of connectivity, called the r-super-connectivity. An n-dimensional torus network is defined as a Cartesian product of n cycles, Ck1× · · ·× Ckn, where Ck j is a cycle of length k j for 1 ≤ j ≤ n. The proposed technique is applied to the two or higher-dimensional torus networks, and their conditional diagnosabilities are established completely: the conditional diagnosability of every torus network G is equal to γ′4(G) + 1, excluding the three small ones C3 ×C3, C3 ×C4, and C4 ×C4. In addition, γp(G) as well as γ′4(G) is derived for 2 ≤ p ≤ 4 and the r-super-connectivity is also derived for 1 ≤ r ≤ 3