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
PDF HTML XML
204
Downloads
341
Views
Citations

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

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.

Share and Cite:

Ren, Y. and Wang, S. (2019) A Proof for g-Good-Neighbor Diagnosability of Exchanged Hypercubes. *American Journal of Computational Mathematics*, **9**, 133-142. doi: 10.4236/ajcm.2019.93010.

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 ${\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{\hspace{0.17em}}\text{foreach}\text{\hspace{0.17em}}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{\ufe38}{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{\hspace{0.17em}}\text{\hspace{0.05em}}\text{for}\text{\hspace{0.17em}}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\text{\hspace{0.17em}}\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|\\ \text{\hspace{0.17em}}\text{\hspace{0.17em}}+\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\text{\hspace{0.17em}}\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.

[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. |

Journals Menu

Copyright © 2021 by authors and Scientific Research Publishing Inc.

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.