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γ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×⋯×CknCk1×⋯×Ckn, where CkjCkj is a cycle of length kjkj for 1≤j≤n1≤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×C3C3×C3, C3×C4C3×C4, and C4×C4C4×C4. In addition, γp(G)γp(G) as well as γ4′(G) is derived for 2≤p≤42≤p≤4 and the r  -super-connectivity is also derived for 1≤r≤31≤r≤3.