Conditional (t,k)-Diagnosis in Regular and Irregular Graphs under the Comparison Diagnosis Model

Assume that there are at most t faulty vertices. A system is conditionally (t,k)-diagnosable if at least k faulty vertices (or all faulty vertices if fewer than k faulty vertices remain) can be identified in each iteration under the assumption that every vertex is adjacent to at least one fault-free vertex. Let κc(G) be the conditional vertex connectivity of G, which measures the vertex connectivity of G according to the assumption that every vertex is adjacent to at least one fault-free vertex. Let Δ (G) be the maximum degrees of the given graph G. When a graph G satisfies the condition that for any pair of vertices with distance two has at least two common neighbors in G, we show the following two results: 1) An r -regular network G containing N vertices is conditionally (N+√ 4κ (G)N}{(r+1)(r-1)}}-2}{r+1},κc(G)) -diagnosable, where r ≥ 3 and N ≥ (r+1)(25r-9)}{4κ (G)}. 2) An irregular network G containing N vertices is conditionally (NΔ (G)+1}-1,κc(G))-diagnosable. By applying the above results to multiprocessor systems, we can measure conditional (t,k)-diagnosabilities for augmented cubes, folded hypercubes, balanced hypercubes, and exchanged hypercubes.