A relationship between g-good-neighbour conditional diagnosability and g-good-neighbour connectivity in regular graphs

摘要

In a system G = (V(G),E(G)), the g-good-neighbour conditional diagnosability t_g(G) is the maximum f such that G is g-good-neighbour f-fault-diagnosable. The g-good-neighbour connectivity κ~(g) (G) is the minimum cardinality of faulty set F is contained in V(G) such that δ(V(G) - F) ≥ g and G-F is disconnected. Under the following three conditions: (1) for any subset S is contained in V(G), if δ(G[S]) ≥ g, then |S| > s; (2) there is a subset A of V(G) with δ(G[A]) ≥ g and |A| = s such that N_G(A) is a minimum g-good-neighbour faulty set and N_G[A] is a g-good-neighbour faulty set;(3) |V(G)| ≥ 2[κ~(g)(G) +s] - 1; in this paper, we find that t_g(G) = κ~(g)(G) +s - 1 holds for k-regular graph G under both PMC model and MM* model, where 2 ≤ g < k and g is an integer.