The pessimistic diagnosability of graphs and its applications to four kinds of interconnection networks

摘要

In a simple graph G= (V(G), E(6)), let n_0 be the minimum cardinality of the neighbourhoods of any two adjacent vertices, i.e. n_0 = min{|N_G({u, v})||(u, v) e E(G)}. Let κ(G) be the connectivity of G. In this paper, we prove that the pessimistic diagnosability of G, denoted by t_p(G), is equal to n_0 if the following two conditions hold: (1) for any subset U is contained in V(G) with 2 ≤ |U| ≤ 2(n_0 - κ(G)), |N_G(U)| ≥ n_0; (2) |V(G)| ≥ 2n_0 + κ(G). As examples of its applications, we prove that the pessimistic diagnosabili-ties of n-dimensional hypercube-like network XQ_n, dual-cube DC_n, pancake network P_n, and burnt pancake graph BP_n are t_p(XQ_n) = 2n - 2 (n ≥ 4), fp(DC_n) = 2n (n≥ 4), t_p(P_n) = 2n - 4 (n ≥ 4) and t_p(BP_n) = 2n - 2 (n ≥ 3), respectively.