Conditional (t, k)-Diagnosis under the PMC Model

In this paper, assuming that each vertex is neighboring to at least one fault-free vertex, we investigate the (t, k)-diagnosability of a graph G under the PMC model. Lower bounds on the numeric degrees of (t, k)-diagnosability are suggested when G is a general graph or G is a regular graph. In particular, the following results are obtained. Symmetric d-dimensional grids are (N-m/2d, min{m, 2d - 1})-diagnosable, where d >= 2, 1 <= m <= 2d - 1, and N are the number of vertices. Symmetric d-dimensional tori are (N+0.62N(2/3)-2/4, 1)-diagnosable if d = 2, and (N-m/2d, min{m, 4d - 2})-diagnosable if d >= 3, where 1 <= m <= 4d - 2. Hypercubes are (N-2logN+2/logN, 2logN - 2)-iagnosable. Cube-connected cycles are (N-m/3, min{m, 4})-diagnosable, where 1 <= m <= 4; k-ary trees are (N-1/k, 1)-diagnosable.