A Proof for g-Good-Neighbor Diagnosability of Exchanged Hypercubes

Yunxia Ren, Shiying Wang

School of Mathematics and Information Science, Henan Normal University, Xinxiang, China.

DOI: 10.4236/ajcm.2019.93010                

Abstract

The diagnosability of a multiprocessor system or an interconnection network is an important research topic. The system and an interconnection network have an underlying topology, which is usually presented by a graph. In this paper, we show proof for the g-good-neighbor diagnosability of the exchanged hypercube EH (s,t) under the PMC model and MM* model.

Keywords

Interconnection Network, Diagnosability, Exchanged Hypercube

1. Introduction

A multiprocessor system and interconnection network have an underlying topology, which is usually presented by a graph, where nodes represent processors and links represent communication links between processors. Some processors may fail in the system and processor fault identification plays an important role in reliable computing. The identification process is called the diagnosis of the system. Several diagnosis models were proposed to identify the faulty processors. One major approach is the Preparata, Metze, and Chien’s (PMC) diagnosis model introduced by Preparata et al. [1] . Under the PMC model, the diagnosis of the system is achieved through two linked processors testing each other. Another major approach, namely, the comparison diagnosis model (MM model), was proposed by Maeng and Malek [2] . Under the MM model, to diagnose a system, a node sends the same task to two of its neighbors, and then compares their responses. The MM^* is a special case of the MM model and each node must test all pairs of its adjacent nodes of the system. The diagnosability of the system is one important study topic. In 2012, Peng et al. [3] proposed measurement for fault diagnosis of the system, namely, the g-good-neighbor diagnosability (which is also called the g-good-neighbor conditional diagnosability), which requires that every fault-free node has at least g fault-free neighbors. Numerous studies have been investigated under the PMC and the MM model or the MM^* model, see [2] - [23] .

Let $EH\left(s,t\right)$ be the exchanged hypercube with $1\le s\le t$. In this paper, we show the following: 1) The g-good-neighbor diagnosability of $EH\left(s,t\right)$ is $2^g\left(s+2-g\right)-1$ under the PMC model for any g with $0\le g\le s$. 2) The diagnosability of $EH\left(s,t\right)$ under the MM^* model is $s+1$ for $2\le s\le t$. 3) The g-good-neighbor diagnosability of $EH\left(s,t\right)$ under the MM^* model is $2^g\left(s+2-g\right)-1$ for $3\le s\le t$ and any g with $0\le g\le s$.

The rest of this paper is organized as follows: In Section 2, we provide the terminology and preliminaries for the system diagnosis. In Section 3, we shall show the g-good-neighbor diagnosability of the exchanged hypercube under the PMC model and the MM^* model. Finally, the conclusion is given in Section 4.

2. Preliminaries

A multiprocessor system and a network are modeled as an undirected simple graph $G=\left(V\left(G\right),E\left(G\right)\right)$, $V\left(G\right)$ denotes processors and $E\left(G\right)$ denotes communication links. For $V^{\prime }\subseteq V\left(G\right)$ with $V^{\prime }\ne \varnothing$, the subgraph of G induced by $V^{\prime }$, denoted by $G\left[V^{\prime }\right]$. For $F_1,F_2\subseteq V\left(G\right)$ with $F_1\ne F_2$, the symmetric difference $F_1\Delta F_2$ is $\left(F_1\setminus F_2\right)\cup \left(F_2\setminus F_1\right)$. For $v\in V\left(G\right)$, the neighborhood $N_G\left(v\right)$ of v in G to be the set of vertices adjacent to v. Let $S\subseteq V\left(G\right)$. The set ${\displaystyle {\cup }_{v\in S}{N}_G\left(v\right)\backslash S}$ is denoted by $N_G\left(S\right)$. For graph-theoretical terminology and notation not defined here we follow [24] .

Let $G=\left(V,E\right)$ be connected. A fault set $F\subseteq V$ is called a g-good-neighbor faulty set if $\left|N\left(v\right)\cap \left(V\backslash F\right)\right|\ge g$ for every vertex v in $V\backslash F$. A g-good-neighbor cut of G is a g-good-neighbor faulty set F such that $G-F$ is disconnected. The minimum cardinality of g-good-neighbor cuts is said to be the g-good-neighbor connectivity of G, denoted by ${\kappa }^{\left(g\right)}\left(G\right)$. A connected graph G is said to be g-good-neighbor connected if G has a g-good-neighbor cut.

Definition 2.1. A system $G=\left(V,E\right)$ is g-good-neighbor t-diagnosable under the PMC model if and only if $\left(F_1,F_2\right)$ is distinguishable for each distinct pair of g-good-neighbor faulty subsets $F_1$ and $F_2$ of V with $\left|F_1\right|\le t$ and $\left|F_2\right|\le t$. The g-good-neighbor diagnosability $t_g\left(G\right)$ of G is the maximum value of t such that G is g-good-neighbor t-diagnosable under the PMC model. In particular, $t_0\left(G\right)=t\left(G\right)$ is said to be the diagnosability of G under the PMC model, $t_1\left(G\right)$ is said to be the nature diagnosability of G under the PMC model.

Definition 2.2. A system $G=\left(V,E\right)$ is g-good-neighbor t-diagnosable under the MM^* model if and only if $\left(F_1,F_2\right)$ is distinguishable for each distinct pair of g-good-neighbor faulty subsets $F_1$ and $F_2$ of V with $\left|F_1\right|\le t$ and $\left|F_2\right|\le t$. The g-good-neighbor diagnosability $t_g\left(G\right)$ of G is the maximum value of t such that G is g-good-neighbor t-diagnosable under the MM^* model. In particular, $t_0\left(G\right)=t\left(G\right)$ is said to be the diagnosability of G under the MM^* model, $t_1\left(G\right)$ is said to be the nature diagnosability of G under the MM^* model.

For a given position integer n, let $\left[n\right]=\left\{1,2,\cdots ,n\right\}$. The sequence $x_n{x}_{n-1}\cdots x_1$ is called a binary string of length n if $x_r\in \left\{0,1\right\}$ for each $r\in \left[n\right]$. Let $x=x_n{x}_{n-1}\cdots x_1$ and $y=y_n{y}_{n-1}\cdots y_1$ be two distinct binary strings of length n.

Hamming distance between x and y, denoted by $H\left(x,y\right)$, is the number of r’s for which $\left|x_r-y_r\right|=1$ for $r\in \left[n\right]$.

For a binary string $u=u_n{u}_{n-1}\cdots u_1{u}_0$ of length $n+1$, we call $u_r$ the r-th bit of u for $r\in \left[n\right]$, and $u_0$ the last bit of u, denote sub-sequence $u_j{u}_{j-1}\cdots u_{i+1}{u}_i$ of u by $u\left[j:i\right]$, i.e., $u\left[j:i\right]=u_j{u}_{j-1}\cdots u_{i+1}{u}_i$. Let $V\left(s,t\right)=\left\{u_{s+t}\cdots u_{t+1}{u}_t\cdots u_1{u}_0:u_0,u_i\in \left\{0,1\right\}\text{foreach}i\in \left[s+t\right]\right\}$.

Definition 2.3. The exchanged hypercube is an undirected graph $EH\left(s,t\right)=\left(V,E\right)$, where $s\ge 1$ and $t\ge 1$ are integers. The set of vertices V is $V\left(s,t\right)$, and the set of edges E is composed of three disjoint types $E_1$, $E_2$ and $E_3$ : $E_1=\left\{uv\in V\times V:u\left[s+t:1\right]=v\left[s+t:1\right],u_0\ne v_0\right\}$, $E_2=\left\{uv\in V\times V:u\left[s+t:t+1\right]=v\left[s+t:t+1\right],H\left(u\left[t:1\right],v\left[t:1\right]\right)=1,u_0=v_0=1\right\}$, $E_3=\left\{uv\in V\times V:u\left[t:1\right]=v\left[t:1\right],H\left(u\left[s+t:t+1\right],v\right)\left[s+t:t+1\right]=1,u_0=v_0=0\right\}$.

3. The g-Good-Neighbor Diagnosability of the Exchanged Hypercube under the PMC and the MM^* Model

Theorem 3.1. [9] For $1\le s\le t$ and any g with $0\le g\le s$, ${\kappa }^{\left(g\right)}\left(EH\left(s,t\right)\right)=2^g\left(s+1-g\right)$.

Let $v_0=0^n=\underset{n}{\underset{︸}{00\cdots 0}}$ and let $V_g=\left\{0^{s-g}{u}_{g+t}\cdots u_{1+t}{0}^{t+1}:u_i=0,1\text{for}i=t+1,t+2,\cdots ,g+t\right\}$. Then $EH\left(s,t\right)\left[V_g\right]\cong Q_g$. By the proof of Lemma 3.1 in [9] , we have the following.

Lemma 3.2. Let $EH\left(s,t\right)$ be the exchanged hypercube with $1\le s\le t$. $V_g$ is defined as above for $0\le g\le s$. Then $\left|V_g\right|=2^g$, $\left|N_{EH\left(s,t\right)}\left(V_g\right)\right|=2^g\left(s+1-g\right)$, and $N_{EH\left(s,t\right)}\left(V_g\right)$ is a g-good-neighbor cut of $EH\left(s,t\right)$.

Theorem 3.3. [19] Let $G=\left(V\left(G\right),E\left(G\right)\right)$ be a g-good-neighbor connected graph, and let H be connected subgraph of G with $\delta \left(H\right)=g$ such that it contains $V\left(G\right)$ as least as possible and $N\left(V\left(H\right)\right)$ is a minimum g-good-neighbor cut of G, and let $H^{\prime }$ be connected subgraph of G with $\delta \left(G\right)=g$ such that it contains $V\left(G\right)$ as least as possible. If $V\left(G\right)\ne F_1\cup F_2$ for each distinct pair of g-good-neighbor faulty subsets $F_1$ and $F_2$ of G with $\left|F_1\right|\le {\kappa }^{\left(g\right)}\left(G\right)+\left|V\left(H^{\prime }\right)\right|-1$ and $\left|F_2\right|\le {\kappa }^{\left(g\right)}\left(G\right)+\left|V\left(H^{\prime }\right)\right|-1$, then ${\kappa }^{\left(g\right)}\left(G\right)+\left|V\left(H^{\prime }\right)\right|-1\le t_g\left(G\right)\le {\kappa }^{\left(g\right)}\left(G\right)+\left|V\left(H\right)\right|-1$ under the PMC model.

Theorem 3.4. Let $EH\left(s,t\right)$ be the exchanged hypercube with $1\le s\le t$ and any g with $0\le g\le s$. Then the g-good-neighbor diagnosability of $EH\left(s,t\right)$ is $2^g\left(s+2-g\right)-1$ under the PMC model.

Proof. Let $V_g$ be defined in Lemma 3.2 for $0\le g\le s$. By the definition of $EH\left(s,t\right)\left[V_g\right]\cong Q_g$, $\left|V\left(Q_g\right)\right|$ is minimum such that $\delta \left(Q_g\right)=g$. Note $2^{s+t+1}>2\left(2^g\left(s+1-g\right)+2^g-1\right)$. Therefore, $V\left(EH\left(s,t\right)\right)\ne F_1\cup F_2$ for each distinct pair of g-good-neighbor faulty subsets $F_1$ and $F_2$ of $EH\left(s,t\right)$ with $\left|F_1\right|\le 2^g\left(s+1-g\right)+2^g-1$ and $\left|F_2\right|\le 2^g\left(s+1-g\right)+2^g-1$. By Theorem 3.4, $t_g\left(EH\left(s,t\right)\right)\ge 2^g\left(s+1-g\right)+2^g-1$. On the other hand, by Lemma 3.2, $N_{EH\left(s,t\right)}\left(V_g\right)$ is a g-good-neighbor cut of $EH\left(s,t\right)$. Since $\left|N_{EH\left(s,t\right)}\left(V_g\right)\right|=2^g\left(s+1-g\right)$, by Theorem 3.1, $N_{EH\left(s,t\right)}\left(V_g\right)$ is a minimum g-good-neighbor cut of $EH\left(s,t\right)$. Note $\left|V_g\right|=2^g$. By Theorem 3.4, $t_g\left(EH\left(s,t\right)\right)\le 2^g\left(s+1-g\right)+2^g-1$. Therefore, $t_g\left(EH\left(s,t\right)\right)=2^g\left(s+1-g\right)+2^g-1$. ,

Before discussing the g-good-neighbor diagnosability of the exchanged hypercube under the MM^* model, we first give two existing results.

Theorem 3.5. [4] [21] A system $G=\left(V,E\right)$ is g-good-neighbor t-diagnosable under the MM^* model if and only if for each distinct pair of g-good-neighbor faulty subsets $F_1$ and $F_2$ of V with $\left|F_1\right|\le t$ and $\left|F_2\right|\le t$ satisfies one of the following conditions. 1) There are two vertices $u,w\in V\setminus \left(F_1\cup F_2\right)$ and there is a vertex $v\in F_1\Delta F_2$ such that $uw\in E$ and $vw\in E$. 2) There are two vertices $u,v\in F_1\setminus F_2$ and there is a vertex $w\in V\setminus \left(F_1\cup F_2\right)$ such that $uw\in E$ and $vw\in E$. 3) There are two vertices $u,v\in F_2\setminus F_1$ and there is a vertex $w\in V\setminus \left(F_1\cup F_2\right)$ such that $uw\in E$ and $vw\in E$.

Theorem 3.6. [19] Let $G=\left(V\left(G\right),E\left(G\right)\right)$ be a g-good-neighbor connected graph, and let H be connected subgraph of G with $\delta \left(H\right)=g$ such that it contains $V\left(G\right)$ as least as possible, and $N\left(V\left(H\right)\right)$ is a minimum g-good-neighbor cut of G. Then the g-good-neighbor diagnosability of G is less than or equal to ${\kappa }^{\left(g\right)}\left(G\right)+\left|V\left(H\right)\right|-1$, i.e., $t_g\left(G\right)\le {\kappa }^{\left(g\right)}\left(G\right)+\left|V\left(H\right)\right|-1$ under the PMC model and MM^* model.

Lemma 3.7. Let $EH\left(s,t\right)$ be the exchanged hypercube with $1\le s\le t$ and any g with $0\le g\le s$. Then the g-good-neighbor diagnosability of the exchanged hypercube $EH\left(s,t\right)$ under the MM^* model is less than or equal to $2^g\left(s+1-g\right)+2^g-1$, i.e., $t_g\left(EH\left(s,t\right)\right)\le 2^g\left(s+2-g\right)-1$.

Proof. Let $V_g$ be defined in Lemma 3.2 for $0\le g\le s$. By the definition of $EH\left(s,t\right)\left[V_g\right]\cong Q_g$, $\left|V\left(Q_g\right)\right|=2^g$ is minimum such that $\delta \left(Q_g\right)=g$. By Lemma 3.2, $N_{EH\left(s,t\right)}\left(V_g\right)$ is a g-good-neighbor cut of $EH\left(s,t\right)$. By Theorems 3.6 and 3.1, $t_g\left(G\right)\le {\kappa }^{\left(g\right)}\left(G\right)+\left|V\left(H\right)\right|-1=2^g\left(s+2-g\right)-1$. ,

A component of a graph G is odd according as it has an odd number of vertices. We denote by $o\left(G\right)$ the number of odd component of G.

Lemma 3.8. [24] A graph $G=\left(V,E\right)$ has a perfect matching if and only if $o\left(G-S\right)\le \left|S\right|$ for all $S\subseteq V$.

Lemma 3.9. [8] Let G be a graph representation of a system. Then the diagnosability $t\left(G\right)\le \delta \left(G\right)$ under the MM^* model.

Theorem 3.10. Let $EH\left(s,t\right)$ be the exchanged hypercube with $2\le s\le t$. Then the 0-good-neighbor diagnosability of $EH\left(s,t\right)$ under the MM^* model is $s+1$, i.e.， $t_0\left(EH\left(s,t\right)\right)=t\left(EH\left(s,t\right)\right)=s+1$.

Proof. By the definition of the g-good-neighbor diagnosability, it is sufficient to show that $EH\left(s,t\right)$ is 0-good-neighbor $\left(s+1\right)$ -diagnosable.

By Theorem 3.5, suppose, on the contrary, that there are two distinct 0-good-neighbor faulty subsets $F_1$ and $F_2$ of $EH\left(s,t\right)$ with $\left|F_1\right|\le s+1$ and $\left|F_2\right|\le s+1$, but the vertex set pair $\left(F_1,F_2\right)$ is not satisfied with any one condition in Theorem 3.5. Without loss of generality, assume that $F_2\setminus F_1\ne \varnothing$. Note $\left|F_1\cup F_2\right|\le \left|F_1\right|+\left|F_2\right|\le 2s+2<2^{s+t+1}$. Therefore, $V\left(EH\left(s,t\right)\right)\ne F_1\cup F_2$.

Note $EH\left(s,t\right)$ has a perfect matching. Let $W\subseteq V\left(EH\left(s,t\right)\right)\setminus \left(F_1\cup F_2\right)$ be the set of isolated vertices in $EH\left(s,t\right)\left[V\left(EH\left(s,t\right)\right)\setminus \left(F_1\cup F_2\right)\right]$, and let H be the subgraph induced by the vertex set $V\left(EH\left(s,t\right)\right)\setminus \left(F_1\cup F_2\cup W\right)$. By Lemma 3.8, $\left|W\right|\le o\left(EH\left(s,t\right)-\left(F_1\cup F_2\right)\right)\le \left|F_1\cup F_2\right|$. Note $2\left|F_1\cup F_2\right|\le 2\left(2s+2\right)<2^{s+t+1}=\left|V\left(EH\left(s,t\right)\right)\right|$. Therefore, $V\left(H\right)\ne \varnothing$. Since $F_1$ and $F_2$ are two distinct 0-good-neighbor faulty sets, and there is no edge between $V\left(EH\left(s,t\right)\right)\setminus \left(F_1\cup F_2\right)$ and $F_1\Delta F_2$, we have that $F_1\cap F_2$ is a 0-good-neighbor cut of $EH\left(s,t\right)$. By Theorem 3.1, we have $\left|F_1\cap F_2\right|\ge s+1$. Therefore, $\left|F_2\right|=\left|F_2\setminus F_1\right|+\left|F_1\cap F_2\right|\ge 1+s+1$, which contradicts $\left|F_2\right|\le s+1$. Therefore, $EH\left(s,t\right)$ is 0-good-neighbor $\left(s+1\right)$ -diagnosable and $t_0\left(EH\left(s,t\right)\right)\ge s+1$. Combining this with Lemma 3.9, we have $t_0\left(EH\left(s,t\right)\right)=t\left(EH\left(s,t\right)\right)=s+1$. ,

Theorem 3.11. Let $EH\left(s,t\right)$ be the exchanged hypercube with $3\le s\le t$. Then the 1-good-neighbor diagnosability of $EH\left(s,t\right)$ under the MM^* model is $2s+1$, i.e., $t_1\left(EH\left(s,t\right)\right)=2s+1$.

Proof. By the definition of 1-good-neighbor diagnosability, it is sufficient to show that $EH\left(s,t\right)$ is 1-good-neighbor $\left(2s+1\right)$ -diagnosable.

By Theorem 3.5, suppose, on the contrary, that there are two distinct 1-good-neighbor faulty subsets $F_1$ and $F_2$ of $EH\left(s,t\right)$ with $\left|F_1\right|\le 2s+1$ and $\left|F_2\right|\le 2s+1$, but the vertex set pair $\left(F_1,F_2\right)$ is not satisfied with any one condition in Theorem 3.5. Without loss of generality, assume that $F_2\setminus F_1\ne \varnothing$. Note $\left|F_1\cup F_2\right|\le \left|F_1\right|+\left|F_2\right|\le 4s+2<2^{s+t+1}$. Therefore, $V\left(EH\left(s,t\right)\right)\ne F_1\cup F_2$.

Claim I. $EH\left(s,t\right)-F_1-F_2$ has no isolated vertex.

Suppose, on the contrary, that $EH\left(s,t\right)-F_1-F_2$ has at least one isolated vertex w. Since $F_1$ is a 1-good neighbor faulty set, there is a vertex $u\in F_2\setminus F_1$ such that u is adjacent to w. Since the vertex set pair $\left(F_1,F_2\right)$ is not satisfied with any one condition in Theorem 3.5, there is at most one vertex $u\in F_2\setminus F_1$ such that u is adjacent to w. Thus, there is just a vertex $u\in F_2\setminus F_1$ such that u is adjacent to w. If $F_1\setminus F_2=\varnothing$, then $F_1\subseteq F_2$. Since $F_2$ is a 1-good neighbor faulty set, $EH\left(s,t\right)-F_2=EH\left(s,t\right)-F_1-F_2$ has not any isolated vertex; a contradiction. Therefore, $F_1\setminus F_2\ne \varnothing$. Similarly, we can deduce that there is just a vertex $v\in F_1\setminus F_2$ such that v is adjacent to w. Let $W\subseteq V\left(EH\left(s,t\right)\right)\setminus \left(F_1\cup F_2\right)$ be the set of isolated vertices in $EH\left(s,t\right)\left[V\left(EH\left(s,t\right)\right)\setminus \left(F_1\cup F_2\right)\right]$, and let H be the subgraph induced by the vertex set $V\left(EH\left(s,t\right)\right)\setminus \left(F_1\cup F_2\cup W\right)$. Then for any $w\in W$, there are $\left(s-1\right)$ neighbors in $F_1\cap F_2$. Note $EH\left(s,t\right)$ has a perfect matching. By Lemma 3.8, $\begin{array}{c}\left|W\right|\le o\left(EH\left(s,t\right)-\left(F_1\cup F_2\right)\right)\le \left|F_1\cup F_2\right|=\left|F_1\right|+\left|F_2\right|-\left|F_1\cap F_2\right|\\ \le 2\left(2s+1\right)-\left(s-1\right)=3s+3\end{array}$. Suppose $V\left(H\right)=\varnothing$. Then $2^{s+t+1}=\left|V\left(EH\left(s,t\right)\right)\right|=\left|F_1\cup F_2\right|+\left|W\right|\le 6s+6$. This is a contradiction to $s\ge 3$. So $V\left(H\right)\ne \varnothing$. Since the vertex set pair $\left(F_1,F_2\right)$ is not satisfied with the condition (1) of Theorem 3.5, and any vertex of $V\left(H\right)$ is not isolated in H, we induce that there is no edge between $V\left(H\right)$ and $F_1\Delta F_2$. Thus, $F_1\cap F_2$ is a vertex cut of $EH\left(s,t\right)$ and $\delta \left(EH\left(s,t\right)-\left(F_1\cap F_2\right)\right)\ge 1$, i.e., $F_1\cap F_2$ is a 1-good-neighbor cut of $EH\left(s,t\right)$. By Theorem 3.1, $\left|F_1\cap F_2\right|\ge 2s$. Because $\left|F_1\right|\le 2s+1$, $\left|F_2\right|\le 2s+1$, and neither $F_1\setminus F_2$ nor $F_2\setminus F_1$ is empty, we have $\left|F_1\setminus F_2\right|=\left|F_2\setminus F_1\right|=1$ and $\left|F_2\cap F_1\right|=2s$. Let $F_1\setminus F_2=\left\{v_1\right\}$ and $F_2\setminus F_1=\left\{v_2\right\}$. Then for any vertex $w\in W$, w are adjacent to $v_1$ and $v_2$. Note that there are at most two common neighbors for any pair of vertices in $EH\left(s,t\right)$, it follows that there are at most two isolated vertices in $EH\left(s,t\right)-F_1-F_2$.

Suppose that there is exactly one isolated vertex v in $EH\left(s,t\right)-F_1-F_2$. Let $v_1$ and $v_2$ be adjacent to v. Then $N_{EH\left(s,t\right)}\left(v\right)\setminus \left\{v_1,v_2\right\}\subseteq F_1\cap F_2$. Since $EH\left(s,t\right)$ contains no triangle, it follows that $N_{EH\left(s,t\right)}\left(v_1\right)\setminus \left\{v\right\}\subseteq F_1\cap F_2$ ; $N_{EH\left(s,t\right)}\left(v_2\right)\setminus \left\{v\right\}\subseteq F_1\cap F_2$ ; $\left[N_{EH\left(s,t\right)}\left(v\right)\setminus \left\{v_1,v_2\right\}\right]\cap \left[N_{EH\left(s,t\right)}\left(v_1\right)\setminus \left\{v\right\}\right]=\varnothing$, $\left[N_{EH\left(s,t\right)}\left(v\right)\setminus \left\{v_1,v_2\right\}\right]\cap \left[N_{EH\left(s,t\right)}\left(v_2\right)\setminus \left\{v\right\}\right]=\varnothing$ and $\left|\left[N_{EH\left(s,t\right)}\left(v_1\right)\setminus \left\{v\right\}\right]\cap \left[N_{EH\left(s,t\right)}\left(v_2\right)\setminus \left\{v\right\}\right]\right|\le 1$.

Thus, $\begin{array}{c}\left|F_1\cap F_2\right|\ge \left|N_{EH\left(s,t\right)}\left(v\right)\setminus \left\{v_1,v_2\right\}\right|+\left|N_{EH\left(s,t\right)}\left(v_1\right)\setminus \left\{v\right\}\right|+\left|N_{EH\left(s,t\right)}\left(v_2\right)\setminus \left\{v\right\}\right|\\ \ge \left(s-1\right)+s+s-1\ge 3s-2\end{array}$. It follows that $\left|F_2\right|=\left|F_2\setminus F_1\right|+\left|F_1\cap F_2\right|\ge 1+3s-2=3s-1>2s+1\left(s\ge 3\right)$, which contradicts $\left|F_2\right|\le 2s+1$.

Suppose that there are exactly two isolated vertices v and w in $EH\left(s,t\right)-F_1-F_2$. Let $v_1$ and $v_2$ be adjacent to v and w, respectively. Then $N_{EH\left(s,t\right)}\left(v\right)\setminus \left\{v_1,v_2\right\}\subseteq F_1\cap F_2$. Since $EH\left(s,t\right)$ contains no triangle, it follows that $N_{EH\left(s,t\right)}\left(v_1\right)\setminus \left\{v,w\right\}\subseteq F_1\cap F_2$, $N_{EH\left(s,t\right)}\left(v_2\right)\setminus \left\{v,w\right\}\subseteq F_1\cap F_2$, $\left[N_{EH\left(s,t\right)}\left(v\right)\setminus \left\{v_1,v_2\right\}\right]\cap \left[N_{EH\left(s,t\right)}\left(v_1\right)\setminus \left\{v,w\right\}\right]=\varnothing$, $\left[N_{EH\left(s,t\right)}\left(v\right)\setminus \left\{v_1,v_2\right\}\right]\cap \left[N_{EH\left(s,t\right)}\left(v_2\right)\setminus \left\{v,w\right\}\right]=\varnothing$ and $\left|\left[N_{EH\left(s,t\right)}\left(v_1\right)\setminus \left\{v,w\right\}\right]\cap \left[N_{EH\left(s,t\right)}\left(v_2\right)\setminus \left\{v,w\right\}\right]\right|=0$.

Thus, $\begin{array}{c}\left|F_1\cap F_2\right|\ge \left|N_{EH\left(s,t\right)}\left(v\right)\setminus \left\{v_1,v_2\right\}\right|+\left|N_{EH\left(s,t\right)}\left(w\right)\setminus \left\{v_1,v_2\right\}\right|\\ +\left|N_{EH\left(s,t\right)}\left(v_1\right)\setminus \left\{v,w\right\}\right|+\left|N_{EH\left(s,t\right)}\left(v_2\right)\setminus \left\{v,w\right\}\right|\\ =\left(s-1\right)+\left(s-1\right)+\left(s-1\right)+\left(s-1\right)=4s-4\end{array}$. It follows that $\left|F_2\right|=\left|F_2\setminus F_1\right|+\left|F_1\cap F_2\right|\ge 1+4s-4=4s-3>2s+1\left(s\ge 3\right)$, which contradicts $\left|F_2\right|\le 2s+1$. The proof of Claim I is complete.

Let $u\in V\left(EH\left(s,t\right)\right)\setminus \left(F_1\cup F_2\right)$. By Claim I, u has at least one neighbor in $EH\left(s,t\right)-F_1-F_2$. Since the vertex set pair $\left(F_1,F_2\right)$ is not satisfied with any one condition in Theorem 3.5, by the condition (1) of Theorem 3.5, for any pair of adjacent vertices $u,w\in V\left(EH\left(s,t\right)\right)\setminus \left(F_1\cup F_2\right)$, there is no vertex $v\in F_1\Delta F_2$ such that $uw\in E\left(EH\left(s,t\right)\right)$ and $vw\in E\left(EH\left(s,t\right)\right)$. It follows that u has no neighbor in $F_1\Delta F_2$. By the arbitrariness of u, there is no edge between $V\left(EH\left(s,t\right)\right)\setminus \left(F_1\cup F_2\right)$ and $F_1\Delta F_2$. Since $F_2\setminus F_1\ne \varnothing$ and $F_1$ is a 1-good-neighbor faulty set, ${\delta }_{EH\left(s,t\right)}\left(\left[F_2\setminus F_1\right]\right)\ge 1$. Note $\left|F_2\setminus F_1\right|\ge 2$. Since both $F_1$ and $F_2$ are 1-good-neighbor faulty sets, and there is no edge between $V\left(EH\left(s,t\right)\right)\setminus \left(F_1\cup F_2\right)$ and $F_1\Delta F_2$, $F_1\cap F_2$ is a 1-good-neighbor cut of $EH\left(s,t\right)$. By Theorem 3.1, $\left|F_1\cap F_2\right|\ge 2s$. Therefore, $\left|F_2\right|=\left|F_2\setminus F_1\right|+\left|F_1\cap F_2\right|\ge 2+2s=2s+2$, which contradicts $\left|F_2\right|\le 2s+1$. Therefore, $EH\left(s,t\right)$ is 1-good-neighbor $\left(2s+1\right)$ -diagnosable and $t_1\left(EH\left(s,t\right)\right)\ge 2s+1$. Combining this with Lemma 3.7, we have $t_1\left(EH\left(s,t\right)\right)=2s+1$. ,

Theorem 3.12. Let $EH\left(s,t\right)$ be the exchanged hypercube with $3\le s\le t$ and any g with $0\le g\le s$. Then the g-good-neighbor diagnosability of the exchanged hypercube $EH\left(s,t\right)$ under the MM^* model is $2^g\left(s+1-g\right)+2^g-1$, i.e., $t_g\left(EH\left(s,t\right)\right)=2^g\left(s+2-g\right)-1$.

Proof. By the definition of the $g$ -good-neighbor diagnosability, it is sufficient to show that $EH\left(s,t\right)$ is g-good-neighbor $\left(2^g\left(s+1-g\right)+2^g-1\right)$ -diagnosable. By Theorems 3.10 and 3.11, it is sufficient to show that $g\ge 2$.

By Theorem 3.5, suppose, on the contrary, that there are two distinct g-good-neighbor faulty subsets $F_1$ and $F_2$ of $EH\left(s,t\right)$ with $\left|F_1\right|\le 2^g\left(s+1-g\right)+2^g-1$ and $\left|F_2\right|\le 2^g\left(s+1-g\right)+2^g-1$, but the vertex set pair $\left(F_1,F_2\right)$ is not satisfied with any one condition in Theorem 3.5. Without loss of generality, assume that $F_2\setminus F_1\ne \varnothing$. It is easy to verify $\left|V\left(EH\left(s,t\right)\right)\right|=2^{s+t+1}>2\left(2^g\left(s+1-g\right)+2^g-1\right)=\left|F_1\cup F_2\right|$. Therefore, $V\left(EH\left(s,t\right)\right)\ne F_1\cup F_2$.

Claim 1. $EH\left(s,t\right)-F_1-F_2$ has no isolated vertex.

Suppose, on the contrary, that $EH\left(s,t\right)-F_1-F_2$ has at least one isolated vertex x. Since $F_1$ is a g-good neighbor faulty set and $g\ge 2$, there are at least two vertices $u,v\in F_2\setminus F_1$ such that $u,v$ are adjacent to x. According to the hypothesis, the vertex set pair $\left(F_1,F_2\right)$ is not satisfied with any one condition in Theorem 3.5. By the condition (3) of Theorem 3.5, there are at most one vertex $u\in F_2\setminus F_1$ such that u are adjacent to x. So $\left|N_{EH\left(s,t\right)-F_1}\left(x\right)\right|\le 1$, a contradiction to that $F_1$ is a g-good neighbor faulty set, where $g\ge 2$. Thus, $EH\left(s,t\right)-F_1-F_2$ has no isolated vertex.

The proof of Claim 1 is complete.

Let $u\in V\left(EH\left(s,t\right)\right)\setminus \left(F_1\cup F_2\right)$. By Claim 1, $\delta \left(EH\left(s,t\right)-F_1-F_2\right)\ge 1$. Since the vertex set pair $\left(F_1,F_2\right)$ is not satisfied with any one condition in Theorem 3.5, by the condition (1) of Theorem 3.5, for any pair of adjacent vertices $u,w\in V\left(EH\left(s,t\right)\right)\setminus \left(F_1\cup F_2\right)$, there is no vertex $v\in F_1\Delta F_2$ such that $uw\in E\left(EH\left(s,t\right)\right)$ and $uv\in E\left(EH\left(s,t\right)\right)$. It follows that u has no neighbor in $F_1\Delta F_2$. By the arbitrariness of u, there is no edge between $V\left(EH\left(s,t\right)\right)\setminus \left(F_1\cup F_2\right)$ and $F_1\Delta F_2$. Since $F_2\setminus F_1\ne \varnothing$ and $F_1$ is a g-good-neighbor faulty set, ${\delta }_{EH\left(s,t\right)}\left(\left[F_2\setminus F_1\right]\right)\ge g$ and $\delta \left(EH\left(s,t\right)-F_2-F_1\right)\ge g$. By the definition of $EH\left(s,t\right)$, $\left|F_2\setminus F_1\right|\ge 2^g$. Since both $F_1$ and $F_2$ are g-good-neighbor faulty sets, and there is no edge between $V\left(EH\left(s,t\right)\right)\setminus \left(F_1\cup F_2\right)$ and $F_1\Delta F_2$, $F_1\cap F_2$ is a g-good-neighbor cut of $EH\left(s,t\right)$. By Theorem 3.1, $\left|F_1\cap F_2\right|\ge 2^g\left(s+1-g\right)$. Therefore, $\left|F_2\right|=\left|F_2\setminus F_1\right|+\left|F_1\cap F_2\right|\ge 2^g+2^g\left(s+1-g\right)$, which contradicts $\left|F_2\right|\le 2^g\left(s+1-g\right)+2^g-1$. Therefore, $EH\left(s,t\right)$ is g-good-neighbor $\left(2^g\left(s+1-g\right)+2^g-1\right)$ -diagnosable and $t_g\left(EH\left(s,t\right)\right)\ge 2^g\left(s+1-g\right)+2^g-1$. Combining this with Lemma 3.7, we have $t_g\left(EH\left(s,t\right)\right)=2^g\left(s+1-g\right)+2^g-1$. ,

4. Conclusion

In this paper, we investigate the problem of the diagnosability of the exchanged hypercube $EH\left(s,t\right)$. We show the following. Let $EH\left(s,t\right)$ be the exchanged hypercube with $3\le s\le t$ and any g with $0\le g\le s$. Then the g-good-neighbor diagnosability of $EH\left(s,t\right)$ under the PMC model and MM^* model is $2^g\left(s+2-g\right)-1$. The work will help engineers to develop more different measures of the diagnosability based on application environment, network topology, network reliability, and statistics related to fault patterns.

Acknowledgements

This work is supported by the National Natural Science Foundation of China (61772010) and the Science Foundation of Henan Normal University (Xiao 20180529, 20180454).

Conflicts of Interest

The authors declare no conflicts of interest regarding the publication of this paper.

References

[1]	Preparata, F.P., Metze, G. and Chien, R.T. (1967) On the Connection Assignment Problem of Diagnosable Systems. IEEE Transactions on Computers, EC-16, 848-854. https://doi.org/10.1109/PGEC.1967.264748
[2]	Maeng, J. and Malek, M. (1981) A Comparison Connection Assignment for Self-Diagnosis of Multiprocessor Systems. Proceeding of 11th International Symposium on Fault-Tolerant Computing, Portland, 24-26 June 1981, 173-175.
[3]	Peng, S.-L., Lin, C.-K., Tan, J.J.M. and Hsu, L.-H. (2012) The g-Good-Neighbor Conditional Diagnosability of Hypercube under PMC Model. Applied Mathematics and Computation, 218, 10406-10412. https://doi.org/10.1016/j.amc.2012.03.092
[4]	Dahbura, A.T. and Masson, G.M. (1984) An Fault Identification Algorithm for Diagnosable Systems. IEEE Transactions on Computers, C-33, 486-492. https://doi.org/10.1109/TC.1984.1676472
[5]	Fan, J. (2002) Diagnosability of Crossed Cubes under the Comparison Diagnosis Model. IEEE Transactions on Parallel and Distributed Systems, 13, 1099-1104. https://doi.org/10.1109/TPDS.2002.1041887
[6]	Hsieh, S.Y. and Kao, C.Y. (2013) The Conditional Diagnosability of k-Ary n-Cubes under the Comparison Diagnosis Model. IEEE Transactions on Computers, 62, 839-843. https://doi.org/10.1109/TC.2012.18
[7]	Lai, P.-L., Tan, J.J.M., Chang, C.-P. and Hsu, L.-H. (2005) Conditional Diagnosability Measures for Large Multiprocessor Systems. IEEE Transactions on Computers, 54, 165-175. https://doi.org/10.1109/TC.2005.19
[8]	Lee, C.-W. and Hsieh, S.-Y. (2013) Diagnosability of Multiprocessor Systems, in: Scalable Computing and Communications: Theory and Practice, Wiley, New York.
[9]	Li, X.-J. and Xu, J.-M. (2013) Generalized Measures of Fault Tolerance in Exchanged Hypercubes. Information Processing Letters, 113, 533-537.
[10]	Ren, Y. and Wang, S. (2017) The g-Good-Neighbor Diagnosability of Locally Twisted Cubes. Theoretical Computer Science, 697, 91-97.
[11]	Wang, M., Guo, Y. and Wang, S. (2017) The 1-Good-Neighbor Diagnosability of Cayley Graphs Generated by Transposition Trees under the PMC Model and MM* Model. International Journal of Computer Mathematics, 94, 620-631. https://doi.org/10.1080/00207160.2015.1119817
[12]	Wang, M., Lin, Y. and Wang, S. (2016) The 2-Good-Neighbor Diagnosability of Cayley Graphs Generated by Transposition Trees under the PMC Model and MM* Model. Theoretical Computer Science, 628, 92-100.
[13]	Wang, M. Lin, Y. and Wang, S. (2018) The 1-Good-Neighbor Connectivity and Diagnosability of Cayley Graphs Generated by Complete Graphs. Discrete Applied Mathematics, 246, 108-118.
[14]	Wang, S. and Han, W. (2016) The g-Good-Neighbor Conditional Diagnosability of n-Dimensional Hypercubes under the MM* Model. Information Processing Letters, 116, 574-577.
[15]	Wang, S., Wang, Z., Wang, M. and Han, W. (2017) The g-Good-Neighbor Conditional Diagnosability of Star Graph Networks under the PMC Model and MM* mode. Frontiers of Mathematics in China, 12, 1221-1234. https://doi.org/10.1007/s11464-017-0657-9
[16]	Wang, S., Wang, Z. and Wang, M. (2017) The 2-Good-Neighbor Connectivity and 2-Good-Neighbor Diagnosability of Bubble-Sort Star Graph Networks. Discrete Applied Mathematics, 217, 691-706.
[17]	Wang, S. and Yang, Y. (2017) The 2-Good-Neighbor (2-Extra) Diagnosability of Alternating Group Graph Networks under the PMC Model and MM* Model. Applied Mathematics and Computation, 305, 241-250.
[18]	Wang, S. and Ma, X. (2018) The g-Extra Connectivity and Diagnosability of Crossed Cubes. Applied Mathematics and Computation, 336, 60-66. https://doi.org/10.1016/j.amc.2018.04.054
[19]	Wang, S. and Wang, M. (2019) The g-Good-Neighbor and g-Extra Diagnosability of Networks. Theoretical Computer Science, 773, 107-114. https://doi.org/10.1016/j.tcs.2018.09.002
[20]	Xu, X., Zhou, S. and Li, J. (2017) Reliability of Complete Cubic Networks under the Condition of g-Good-Neighbor. The Computer Journal, 60, 625-635. https://doi.org/10.1093/comjnl/bxw078
[21]	Yuan, J., Liu, A., Ma, X., Liu, X., Qin, X. and Zhang, J. (2015) The g-Good-Neighbor Conditional Diagnosability of k-Aryn-Cubes under the PMC Model and MM* Model. IEEE Transactions on Parallel and Distributed Systems, 26, 1165-1177. https://doi.org/10.1109/TPDS.2014.2318305
[22]	Yuan, J., Liu, A., Qin, X., Zhang, J. and Li, J. (2016) g-Good-Neighbor Conditional Diagnosability Measures for 3-Ary n-Cube Networks. Theoretical Computer Science, 622, 144-162. https://doi.org/10.1016/j.tcs.2016.01.046
[23]	Zheng, J., Latifi, S., Regentova, E., Luo, K. and Wu, X. (2005) Diagnosability of Star Graphs under the Comparison Diagnosis Model. Information Processing Letters, 93, 29-36. https://doi.org/10.1016/j.ipl.2004.09.011
[24]	Bondy, J.A. and Murty, U.S.R. (2007) Graph Theory. Springer, New York.