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.62 N^{{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-2log N+2 log N},2log N-2)-diagnosable. Cube-connected cycles are ({N-m 3}, {min} \{m, 4\} )-diagnosable, where 1≤ m ≤ 4; k-ary trees are ({N-1 k}, 1)-diagnosable.