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, gamma(p) (resp. gamma(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, Ck(1) x ... x C-kn, where C-kj 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 gamma(4)'(G) + 1, excluding the three small ones C-3 x C-3, C-3 x C-4, and C-4 x C-4. In addition, gamma(p)(G) as well as gamma(4)'(G) is derived for 2 <= p <= 4 and the r-superconnectivity is also derived for 1 <= r <= 3. (C) 2014 Elsevier B.V. All rights reserved.