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-mover 2d}, {min} {m, 2d-1} )-diagnosable, where dge 2, 1le mle 2d-1, and N are the number of vertices. Symmetric d-dimensional tori are ({N+0.62 N^{{2over 3} }-2over 4},1)-diagnosable if d=2, and ({N-mover 2d}, {min} {m, 4d-2} )-diagnosable if dge 3, where 1le mle 4d-2. Hypercubes are ({N-2log N+2over log N},2log N-2)-diagnosable. Cube-connected cycles are ({N-mover 3}, {min} {m, 4} )-diagnosable, where 1le m le 4; k-ary trees are ({N-1over k}, 1)-diagnosable.