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

ABSTRACT

In a simple graph $G=\left(V\right(G),E(G\left)\right)$, let $n_0$ be the minimum cardinality of the neighbourhoods of any two adjacent vertices, i.e. $n_0=min\left\{|N_G\right(\{u,v\}\left)||\right(u,v)\in E(G\left)\right\}$. Let $\kappa \left(G\right)$ be the connectivity of G. In this paper, we prove that the pessimistic diagnosability of G, denoted by $t_p\left(G\right)$, is equal to $n_0$ if the following two conditions hold: (1) for any subset $U\subset V\left(G\right)$ with $2\le |U|\le 2(n_0-\kappa (G\left)\right)$, $|N_G\left(U\right)|\ge n_0$; (2) $|V\left(G\right)|\ge 2n_0+\kappa \left(G\right)$. As examples of its applications, we prove that the pessimistic diagnosabilities of n-dimensional hypercube-like network $X{Q}_n$, dual-cube $D{C}_n$, pancake network $P_n$, and burnt pancake graph $B{P}_n$ are $t_p\left(X{Q}_n\right)=2n-2$ ($n\ge 4$), $t_p\left(D{C}_n\right)=2n$ ($n\ge 4$), $t_p\left(P_n\right)=2n-4$ ($n\ge 4$) and $t_p\left(B{P}_n\right)=2n-2$ ($n\ge 3$), respectively.

KEYWORDS:

• Pessimistic diagnosability
• interconnection networks
• PMC model
• fault-tolerance
• neighbourhood

2010 AMS SUBJECT CLASSIFICATIONS:

• 94C12
• 94C15

Disclosure statement

No potential conflict of interest was reported by the author.

ORCID

Dongqin Cheng  http://orcid.org/0000-0001-9933-6601

Additional information

Funding

This work was supported by the Fundamental Research Funds for the Central Universities of China [grant number 21616311].