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\over 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.62 2/3-2/4,1)-diagnosable if d=2, and (N-m 2d m, 4d-2)-diagnosable if d≥ 3, where 1≤ m≤ 4d-2. Hypercubes are (N-2 N+2 N ,2 N-2)-diagnosable. Cube-connected cycles are (N-m 3, m, 4)-diagnosable, where 1≤ m ≤ 4; k-ary trees are (N-1 k, 1)-diagnosable.