The pessimistic diagnosability of graphs and its applications to four kinds of interconnection networks
Dongqin Cheng · International Journal of Computer Mathematics Computer Systems Theory · 2019
In a simple graph G=(V(G),E(G)), let n0 be the minimum cardinality of the neighbourhoods of any two adjacent vertices, i.e. n0=min{|NG({u,v})||(u,v)∈E(G)}. Let κ(G) be the connectivity of G. In this paper, we prove that the pessimistic diagnosability of G, denoted by tp(G), is equal to n0 if the following two conditions hold: (1) for any subset U⊂V(G) with 2≤|U|≤2(n0−κ(G)), |NG(U)|≥n0; (2) |V(G)|≥2n0+κ(G). As examples of its applications, we prove that the pessimistic diagnosabilities of n-dimensional hypercube-like network XQn, dual-cube DCn, pancake network Pn, and burnt pancake graph BPn are tp(XQn)=2n−2 (n≥4), tp(DCn)=2n (n≥4), tp(Pn)=2n−4 (n≥4) and tp(BPn)=2n−2 (n≥3), respectively.