# Reliability Evaluation of Generalized ExchangedX-Cubes Based on the Condition of g-Good-Neighbor

Authors: Xiaoyan Li; Hongbin Zhuang; Shuming Zhou; Hongju Cheng; Cheng-Kuan Lin; Wenzhong Guo
Journal: Wireless Communications and Mobile Computing
 (2020)

---

## Abstract

In the cloud computing environment with massive information services and decision-making resources, the accuracy and reliability of information are more important than previous single closed systems. Therefore, ensuring the reliability of information and the stable operation of the system are the core problems in the research fields such as the Internet Plus and the Internet of Things. The connectivity and diagnosability are two important measures for the fault tolerance of multiprocessor systems. Theg-good-neighbor conditional connectivity (Rg-connectivity) is the minimum number of nodes that make the graph disconnected, and each node has at least g neighbors in every remaining component. The g-good-neighbor conditional diagnosability (g-GNCD) is the maximum number of faulty processors that has been correctly identified in a system, and any fault-free processor has no less than g fault-free neighbors. Exchanged X-cubes are a class of irregular networks, obtained by deleting links from hypercubes and some variant networks of hypercubes (X-cubes). They not only combine the advantages of X-cubes but also reduce the interconnection complexity. Exchanged X-cubes classify its nodes into two different classes clusters with a unique connecting rule. In this paper, we propose the generalized exchanged X-cubes framework so that architecture can be constructed by different connecting rules. Furthermore, we study the Rg-connectivity and g-GNCD of generalized exchanged X-cubes under the PMC and MM∗ models. As applications, the Rg-connectivity and g-GNCD of generalized exchanged hypercubes, dual-cube-like networks, generalized exchanged crossed cubes, and locally generalized exchanged twisted cubes are determined, respectively.


---

## Body

## 1. Introduction

With the expansion of network scale and the improvement of complexity, the reliability and stability of the system become more and more important. How to ensure the correct and efficient operation of the system is an important research topic for wireless sensor networks and distributed systems. The distributed system disperses the computing tasks which are originally collected on one computer to polymorphic computer for parallel processing. It has many advantages, such as resource sharing, openness, concurrency, scalability, and fault tolerance. In the operation of the multiprocessor system, processor failure is inevitable. It may slow down the communication of information or even lead to paralyze of the system, thereby affecting the normal operation of the multiprocessor system and bringing huge losses. For example, on Google and Amazon systems, the failure of processors (servers) for several hours can bring millions of dollars of losses. Therefore, fault tolerance is very important for the construction and maintenance of systems [1, 2]. In fact, a multiprocessor system can be usually enlightened as a simple connected graph, where each processor represents a node of the graph, and each link between two processors represents an edge between two nodes in the graph. The graph is called the interconnection network of this multiprocessor system. Thus, some parameters of a graph as an interconnection network can be used to measure the reliability of a multiprocessor system. In the following, we do not distinguish among multiprocessor systems, interconnection networks, and graphs.An important evaluating parameter for the fault tolerance of a system (modeled by graphG), the connectivity, is denoted by κG, which is the minimum number of nodes that make the graph disconnected. So far, connectivities for many famous networks have been proven. Nevertheless, there is a shortcoming for using traditional connectivity as a parameter of fault tolerance, which is considered a highly unlikely phenomenon in reality that all nodes adjacent to a node have failed simultaneously. Therefore, Esfahanian and Hakimi [3] proposed a new measure to overcome this shortcoming, the restricted connectivity, which limits that all adjacent nodes of any node cannot fail at the same time. Later, a generalized restricted connectivity concept, the g-restricted connectivity (Rg-connectivity), was proposed by Latifi et al. [4], which defines that each node of any remaining component after deleting all faulty nodes has degree at least g. In recent years, they have attracted much interest of theoretical computer scientists and mathematicians. Xu et al. [5] determined the Rg-connectivity of hierarchical cubic networks and complete cubic networks. Ning [6] studied the Rg-connectivity of exchanged crossed cubes. Yuan et al. [7] explored the Rg-connectivity of κ-ary n-cube networks. Lin et al. [8] obtained the Rg-connectivity of (n,k)-arrangement graphs.Identifying all faulty processors in a multiprocessor system (in brief, system) is calledsystem-level diagnosis. A system is t-diagnosable when all faulty processors can be detected, provided that the number of faulty processors in it does not exceed t. The maximum number of faulty processors that the system can precisely point out is as known as the diagnosability of the system. In system-level diagnosis, there are several well-known models.ThePMC model is the first model, proposed by Preparate et al. [9], which is a test-based model, assumes that the adjacent processors can perform tests on each other. For any adjacent processors in a system, the ordered pair x,y is called a test that x diagnoses its neighbor y, where x is a tester and y is a testee. In case x diagnoses y to be faulty (resp., fault-free), the outcome of the test x,y is 1 (resp., 0). Moreover, the outcome is reliable in the present of the tester x is fault-free. Another model, the MM model, was proposed by Maeng and Malek [10], which is a comparison-based model. In MM model, a comparator processor z sends the same test to its two neighbors x,y (i.e., comparison nodes) and then compares their responses. Let a labeled edge x,yz be a comparison performed that two processors x and y are compared by a processor z, where x is adjacent to z and y is also adjacent to z. If the comparator processor z is fault-free, and the responses of x and y are identical, then both comparison processors x and y are fault-free; on the other hand, if the responses of x and y are different, then at least one of x,y is faulty. Furthermore, if both comparison processors x and y are faulty, the responses of x and y are distinct. In addition, the comparison x,yz is unreliable in the present if the comparator node z is faulty. The MM∗model (proposed by Sengupta and Dahbura) [11] is a special MM model, which is assumed that each processor must compare each pair of its adjacent processors.Since there is no restrictive condition on the distribution pattern of faulty processors, the classical diagnosability of a system is quite small. In order to increase the diagnosability, Lai et al. [12] proposed a more realistic parameter of diagnosability, conditional diagnosability, which limited that all the neighbors of any processor cannot be faulty at the same time in a system. Recently, Peng et al. [13] proposed the notion of g-good-neighbor conditional diagnosability (g-GNCD), which is the maximum number of faulty processors that can be identified under the condition that every fault-free processor has no less than g fault-free neighbors. Peng et al. [13] (resp., Wang et al. [14]) established the g-GNCD of hypercubes under the PMC model (resp., MM∗ model). Li et al. [15] introduced the diagnosability and 1-good-neighbor conditional diagnosability of hypercubes with missing links and broken-down nodes under the PMC model. Yuan et al. [7] studied the g-good-neighbor conditional diagnosabilities of k-ary n-cube networks under the PMC model and the MM∗ model. Xu et al. [5] established the g-good-neighbor conditional diagnosabilities of complete cubic networks under the PMC model and the MM∗ model. Lin et al. [16] evaluated the g-good-neighbor conditional diagnosabilities of n,k-arrangement graphs under the PMC model and the MM∗ model. Guo et al. [17] studied the g-good-neighbor conditional diagnosability of the crossed cubes under the PMC model and the MM∗ model. Li et al. [18] introduced this concept into a family of data center networks—DCell—and determined the g-good-neighbor conditional diagnosabilities of DCell under the PMC model and the MM∗ model.TheRg-connectivity (or g-GNCD) of different networks are usually determined independently. It is a very worthwhile topic to explore a unified method to get them in different networks. A family of exchanged networks (i.e., exchanged X-cubes) have some common properties, so that their Rg-connectivity (or g-GNCD) can be studied by a uniform method. The family of exchanged X-cubes not only combine the advantages of hypercubes and some variant networks of hypercubes (X-cubes) but also reduce the interconnection complexity. Exchanged X-cubes classify its nodes into two different classes clusters with a unique connecting rule. In this paper, we propose the generalized exchanged X-cubes framework so that architecture can be constructed by different connecting rules. There are some of the better properties in generalized exchanged X-cubes, such as smaller diameter, fewer edges, lower cost factor, and low latency. Based on the fine properties, the network’s hardware and communication costs are reduced, and a greater balance between performance and cost can be achieved. Due to the excellent properties of the generalized exchanged X-cubes, they can be used as the logical topologies in the peer-to-peer environment [19].In recent years, the research on the relationship between theRg-connectivity and the g-GNCD of regular networks under certain conditions has been widely developed [20–24], while this paper will study the Rg-connectivity and the g-GNCD of a class of irregular networks (i.e., generalized exchanged X-cubes). We first establish the Rg-connectivity of generalized exchanged X-cubes. Next, we evaluate the g-GNCD of generalized exchanged X-cubes. As applications, we obtain the Rg-connectivity and g-GNCD of generalized exchanged hypercubes, dual-cube-like networks, generalized exchanged crossed cubes, and locally generalized exchanged twisted cubes.The remainder of this paper is organized as follows. Section2 provides the terms and notations used throughout the paper. Section 3 evaluates the Rg-connectivity of generalized exchanged X-cubes. Section 4 establishes the g-GNCD of generalized exchanged X-cubes. Section 5 gives some applications based on the results in Section 3 and Section 4. In Section 6, we illustrate the advantages of Rg-connectivity and g-GNCD compared to traditional connectivity and traditional diagnosability, respectively. Finally, we finish the whole paper by concluding in Section 7.


## 2. Preliminaries

### 2.1. Terminology and Notations

In this paper, a multiprocessor system is usually represented by a simple undirected graph (in brief, a graph). For terminology and notations not defined in this paper, we follow the reference [25]. We use G=VG,EG to represent a graph, where VG representing a nonempty and finite node set and EG=u,v∣u,v is an unordered pair of VG representing an edge set. Two nodes u and v are adjacent, denoted by u,v∈EG. The set of neighbors of node u in G is denoted by NGu=v∈VG∣u,v∈EG. If R⊆VG, let GR denote the subgraph of G induced by the node subset R in G. And we denote G−R as GVG∖R. We set NGR=v∈VG\R∣u,v∈EGandu∈R=⋃u∈RNGu\R and NGR=NGR∪R. Two binary strings u=u1u0 and v=v1v0 are pair related, denoted by u∼v, if and only if u,v∈00,00,01,11,10,10,11,01. The case that u and v are not pair related is denoted by u≁v[26].Thedegree of u in G is denoted by degGu=NGu. Let δG=mindegGu∣u∈VG, ΔG=maxdegGu∣u∈VG. Kn is defined as a complete graph with n nodes. A pathP is a sequence of distinct nodes with any two consecutive nodes in P that are adjacent. We use G1≅G2 to represent the graph G1 is isomorphic to the graph G2. A component is defined as a maximally connected subgraph of a graph.Definition 1 (see [27]).
LetR⊆VG. R is called a node-cut if G−R is disconnected. If there exists a node-cut R with R=k, then R is called a k-node-cut. The connectivity κG of G is defined as the minimum k such that G has a k-node-cut.Definition 2 (see [4]).
Letg be a positive integer and R⊆VG. If G−R is disconnected and each remaining component has minimum degree at least g, then R is called an Rg-cut.Definition 3 (see [4]).
TheRg-connectivity of G, denoted by κgG, is the minimum cardinality over all Rg-cuts of G.


### 2.2. Theg-Good-Neighbor Conditional Diagnosability

Under the PMC model and MM∗ model, we call the notation Ω as the syndrome of the system, which is defined as the set of all test (comparison) results in a system G, where test results are based on the PMC model and comparison results are based on the MM∗ model. Define a faulty set F, where ∀i∈F, i is a faulty processor. Let ΩF be the set of test (comparison) results which could be produced if F is the faulty node set. We use F1^ and F2^ to represent two distinct faulty sets of VG. In case ΩF1^∩ΩF2^=∅, we call these two distinct faulty sets F1^ and F2^distinguishable, and F1^,F2^ a distinguishable pair; otherwise, F1^ and F2^ are indistinguishable, and F1^,F2^ is an indistinguishable pair. Let F1^△F2^ be the symmetric difference F1^−F2^∪F2^−F1^ between F1^ and F2^. In [28], under the PMC model, the sufficient and necessary condition for two different subsets F1^ and F2^ is a distinguishable pair proposed by Dahbura and Masson. Moreover, under the MM∗ model, the sufficient and necessary condition for two different subsets F1^ and F2^ is a distinguishable pair proposed by Sengupta and Dahbura [11].Lemma 4 (see [28]).
LetG=VG,EG be a multiprocessor system. For any two distinct sets F1^,F2^⊆VG, F1^ and F2^ are distinguishable under the PMC model if and only if there exists at least one test from VG−F1^∪F2^ to F1^△F2^ (see Figure 1(a)).Lemma 5 (see [11]).
LetG=VG,EG be a multiprocessor system. For any two distinct sets F1^,F2^⊆VG, F1^ and F2^ are distinguishable under the MM∗ model if and only if there is a node w∈VG−F1^∪F2^ such that one of the following conditions holds (see Figure 1(b)):
(1)
NGw−F1^∪F2^≥1 and NGw∩F1^ΔF2^≥1,(2)
NGw∩F1^−F2^≥2,(3)
N¯Gw∩F¯2∧−F¯1∧≥2.Figure 1
(a) An illustration for Lemma4. (b) An illustration for Lemma 5.
(a)(b)The concept ofg-GNCD of a system was proposed in the literature [13].Definition 6 (see [13]).
(1)
LetF^⊆VG and F^ be a fault-set. If any node of VG−F^ has at least g neighbors in G−F^, then F^ is called a g-good-neighbor conditional fault-set.(2)
A systemG is g-good-neighbor conditional t-diagnosable if each distinct pair of g-good-neighbor conditional faulty (g-GNCF) sets F1^ and F2^ of VG with F1^≤t and F2^≤t are distinguishable.(3)
Theg-GNCD, denoted by tgG, is defined as the maximum value of t such that G is g-good-neighbor conditionally t-diagnosable. Let tgPG and tgMG be the g-GNCD of G under the PMC model and MM∗ model, respectively.


### 2.3. Generalized ExchangedX-Cubes

In this subsection, we give the definition of the family of generalized exchanged networks, denoted bygeneralized exchangedX-cubes, which have some common properties, so that the their Rg-connectivity (or g-GNCD) can be studied by a uniform method. Since generalized exchanged X-cubes are derived by BC networks (bijective connection networks), we first review the definition of the BC network.Definition 7 (see [29]).
The one-dimensional BC networkX1 contains only two nodes which forms an edge. We use L1 to represent the family of the one-dimensional BC network with L1=X1. A graph G belongs to the family of n-dimensional BC networks Ln if and only if there exists V0,V1⊂VG such that the following two conditions hold:
(1)VG=V0∪V1,V0≠∅,V1≠∅,V0∩V1=∅,andGV0,GV1∈Ln−1
EV0,V1 is a perfect matching M between V0 and V1 in GFor anyXn∈Ln, by Definition 7, there exist V0,V1,M satisfying the conditions. We use Xn−10, Xn−11 to denote the induced subgraph GV0, GV1, respectively. Clearly, they are both n−1-dimensional BC networks, and EXn−10, EXn−11, M is a decomposition of EXn. We define the decomposition as Xn=GXn−10,Xn−11;M.BC networks are a class of networks containing a number of famous networks such as hypercubes [13], the Möbius cubes [30], crossed cubes [31], and locally twisted cubes [32] as members. An n-dimensional BC network Xn is n-regular and consisting of 2n nodes. Figure 2 shows two three-dimensional BC networks.Lemma 8 (see [33]).
For0≤g≤n and Y⊂VXn, ifδXnY≥g, then Y≥2g.Lemma 9 (see [34]).
(1)
ForY⊂VXn and 0≤g≤n, if δXnY=g, then NXnY≥n−g2g.(2)
For0≤g≤n−2, κgXn=n−g2g.Lemma 10 (see [35]).
Forn≥2, there are at most two common neighbors between any two nodes of Xn.Figure 2
Two three-dimensional BC networks.
(a)(b)Next, we introduce the definition of generalized exchangedX-cubes.Definition 11.
Thes,t-dimensional generalized exchanged X-cubes is defined as a graph GEXs,t=VGEXs,t,EGEXs,t, for s≥1 and t≥1. GEXs,t consists of two disjoint subgraphs L′~ and R′~. And L′~ consists of 2t subgraphs, denoted by Li′~ for i=1,2,⋯,2t. Similarly, R′~ consists of 2s subgraphs, denoted by Rj′~ for j=1,2,⋯,2s. Moreover, GEXs,t satisfies the following conditions (see Figure 3):
(a)
For any integers1≤i≤2t and 1≤j≤2s, Li′~≅Xs and Rj′~≅Xt. Further, VLi′~=2s and VRj′~=2t(b)
Each node inVL′~ has a sole neighbor in VR′~ and vice versa. In addition, for distinct nodes in each Li′~, their neighbors of R′~ lie in different Rj′~(c)
For any two different subgraphsLi′~ and Lh′~ with i≠h, there exists no edge between them. Similar for Rj′~ and Rk′~ with j≠k.Figure 3
(a) The partition ofGEXs,t. (b) The contraction of GEXs,t.
(a)(b)By Definition11, we can deduce that VGEXs,t=2s+t+1. Let each of Li′~ and Rj′~ be a cluster of GEXs,t. Obviously, GEXs,t consists of 2t+2s clusters. If we contract each cluster as a node, then GEXs,t is contracted into a complete bipartite graph K2t,2s. The edges that connect different clusters are called cross edges. In the following discussion, we consider s≤t, and thus, δGEXs,t=s+1, ΔGEXs,t=t+1.


## 2.1. Terminology and Notations

In this paper, a multiprocessor system is usually represented by a simple undirected graph (in brief, a graph). For terminology and notations not defined in this paper, we follow the reference [25]. We use G=VG,EG to represent a graph, where VG representing a nonempty and finite node set and EG=u,v∣u,v is an unordered pair of VG representing an edge set. Two nodes u and v are adjacent, denoted by u,v∈EG. The set of neighbors of node u in G is denoted by NGu=v∈VG∣u,v∈EG. If R⊆VG, let GR denote the subgraph of G induced by the node subset R in G. And we denote G−R as GVG∖R. We set NGR=v∈VG\R∣u,v∈EGandu∈R=⋃u∈RNGu\R and NGR=NGR∪R. Two binary strings u=u1u0 and v=v1v0 are pair related, denoted by u∼v, if and only if u,v∈00,00,01,11,10,10,11,01. The case that u and v are not pair related is denoted by u≁v[26].Thedegree of u in G is denoted by degGu=NGu. Let δG=mindegGu∣u∈VG, ΔG=maxdegGu∣u∈VG. Kn is defined as a complete graph with n nodes. A pathP is a sequence of distinct nodes with any two consecutive nodes in P that are adjacent. We use G1≅G2 to represent the graph G1 is isomorphic to the graph G2. A component is defined as a maximally connected subgraph of a graph.Definition 1 (see [27]).
LetR⊆VG. R is called a node-cut if G−R is disconnected. If there exists a node-cut R with R=k, then R is called a k-node-cut. The connectivity κG of G is defined as the minimum k such that G has a k-node-cut.Definition 2 (see [4]).
Letg be a positive integer and R⊆VG. If G−R is disconnected and each remaining component has minimum degree at least g, then R is called an Rg-cut.Definition 3 (see [4]).
TheRg-connectivity of G, denoted by κgG, is the minimum cardinality over all Rg-cuts of G.


## 2.2. Theg-Good-Neighbor Conditional Diagnosability

Under the PMC model and MM∗ model, we call the notation Ω as the syndrome of the system, which is defined as the set of all test (comparison) results in a system G, where test results are based on the PMC model and comparison results are based on the MM∗ model. Define a faulty set F, where ∀i∈F, i is a faulty processor. Let ΩF be the set of test (comparison) results which could be produced if F is the faulty node set. We use F1^ and F2^ to represent two distinct faulty sets of VG. In case ΩF1^∩ΩF2^=∅, we call these two distinct faulty sets F1^ and F2^distinguishable, and F1^,F2^ a distinguishable pair; otherwise, F1^ and F2^ are indistinguishable, and F1^,F2^ is an indistinguishable pair. Let F1^△F2^ be the symmetric difference F1^−F2^∪F2^−F1^ between F1^ and F2^. In [28], under the PMC model, the sufficient and necessary condition for two different subsets F1^ and F2^ is a distinguishable pair proposed by Dahbura and Masson. Moreover, under the MM∗ model, the sufficient and necessary condition for two different subsets F1^ and F2^ is a distinguishable pair proposed by Sengupta and Dahbura [11].Lemma 4 (see [28]).
LetG=VG,EG be a multiprocessor system. For any two distinct sets F1^,F2^⊆VG, F1^ and F2^ are distinguishable under the PMC model if and only if there exists at least one test from VG−F1^∪F2^ to F1^△F2^ (see Figure 1(a)).Lemma 5 (see [11]).
LetG=VG,EG be a multiprocessor system. For any two distinct sets F1^,F2^⊆VG, F1^ and F2^ are distinguishable under the MM∗ model if and only if there is a node w∈VG−F1^∪F2^ such that one of the following conditions holds (see Figure 1(b)):
(1)
NGw−F1^∪F2^≥1 and NGw∩F1^ΔF2^≥1,(2)
NGw∩F1^−F2^≥2,(3)
N¯Gw∩F¯2∧−F¯1∧≥2.Figure 1
(a) An illustration for Lemma4. (b) An illustration for Lemma 5.
(a)(b)The concept ofg-GNCD of a system was proposed in the literature [13].Definition 6 (see [13]).
(1)
LetF^⊆VG and F^ be a fault-set. If any node of VG−F^ has at least g neighbors in G−F^, then F^ is called a g-good-neighbor conditional fault-set.(2)
A systemG is g-good-neighbor conditional t-diagnosable if each distinct pair of g-good-neighbor conditional faulty (g-GNCF) sets F1^ and F2^ of VG with F1^≤t and F2^≤t are distinguishable.(3)
Theg-GNCD, denoted by tgG, is defined as the maximum value of t such that G is g-good-neighbor conditionally t-diagnosable. Let tgPG and tgMG be the g-GNCD of G under the PMC model and MM∗ model, respectively.


## 2.3. Generalized ExchangedX-Cubes

In this subsection, we give the definition of the family of generalized exchanged networks, denoted bygeneralized exchangedX-cubes, which have some common properties, so that the their Rg-connectivity (or g-GNCD) can be studied by a uniform method. Since generalized exchanged X-cubes are derived by BC networks (bijective connection networks), we first review the definition of the BC network.Definition 7 (see [29]).
The one-dimensional BC networkX1 contains only two nodes which forms an edge. We use L1 to represent the family of the one-dimensional BC network with L1=X1. A graph G belongs to the family of n-dimensional BC networks Ln if and only if there exists V0,V1⊂VG such that the following two conditions hold:
(1)VG=V0∪V1,V0≠∅,V1≠∅,V0∩V1=∅,andGV0,GV1∈Ln−1
EV0,V1 is a perfect matching M between V0 and V1 in GFor anyXn∈Ln, by Definition 7, there exist V0,V1,M satisfying the conditions. We use Xn−10, Xn−11 to denote the induced subgraph GV0, GV1, respectively. Clearly, they are both n−1-dimensional BC networks, and EXn−10, EXn−11, M is a decomposition of EXn. We define the decomposition as Xn=GXn−10,Xn−11;M.BC networks are a class of networks containing a number of famous networks such as hypercubes [13], the Möbius cubes [30], crossed cubes [31], and locally twisted cubes [32] as members. An n-dimensional BC network Xn is n-regular and consisting of 2n nodes. Figure 2 shows two three-dimensional BC networks.Lemma 8 (see [33]).
For0≤g≤n and Y⊂VXn, ifδXnY≥g, then Y≥2g.Lemma 9 (see [34]).
(1)
ForY⊂VXn and 0≤g≤n, if δXnY=g, then NXnY≥n−g2g.(2)
For0≤g≤n−2, κgXn=n−g2g.Lemma 10 (see [35]).
Forn≥2, there are at most two common neighbors between any two nodes of Xn.Figure 2
Two three-dimensional BC networks.
(a)(b)Next, we introduce the definition of generalized exchangedX-cubes.Definition 11.
Thes,t-dimensional generalized exchanged X-cubes is defined as a graph GEXs,t=VGEXs,t,EGEXs,t, for s≥1 and t≥1. GEXs,t consists of two disjoint subgraphs L′~ and R′~. And L′~ consists of 2t subgraphs, denoted by Li′~ for i=1,2,⋯,2t. Similarly, R′~ consists of 2s subgraphs, denoted by Rj′~ for j=1,2,⋯,2s. Moreover, GEXs,t satisfies the following conditions (see Figure 3):
(a)
For any integers1≤i≤2t and 1≤j≤2s, Li′~≅Xs and Rj′~≅Xt. Further, VLi′~=2s and VRj′~=2t(b)
Each node inVL′~ has a sole neighbor in VR′~ and vice versa. In addition, for distinct nodes in each Li′~, their neighbors of R′~ lie in different Rj′~(c)
For any two different subgraphsLi′~ and Lh′~ with i≠h, there exists no edge between them. Similar for Rj′~ and Rk′~ with j≠k.Figure 3
(a) The partition ofGEXs,t. (b) The contraction of GEXs,t.
(a)(b)By Definition11, we can deduce that VGEXs,t=2s+t+1. Let each of Li′~ and Rj′~ be a cluster of GEXs,t. Obviously, GEXs,t consists of 2t+2s clusters. If we contract each cluster as a node, then GEXs,t is contracted into a complete bipartite graph K2t,2s. The edges that connect different clusters are called cross edges. In the following discussion, we consider s≤t, and thus, δGEXs,t=s+1, ΔGEXs,t=t+1.


## 3. TheRg-Connectivity of GEXs,t

In this section, we establish theRg-connectivity of GEXs,t with 1≤g≤s−2. In what follows, we exploit some useful lemmas for our further investigation.Lemma 12.
For any integerss≥3 and 1≤g≤s, let H be a subgraph of Xs with δH≥g, and let T be a subgraph of Xs such that T≅Xg. Then NXsH≥NXsT=s−g+12g.Proof.
We conduct induction ons.
Ifs=3, by fixing g, the lemma holds obviously. Suppose that the lemma holds for s=τ−1, let H be a subgraph of Xτ−1 with δH≥g and T1 be a subgraph of Xτ−1 such that T1≅Xg, then NXτ−1H≥NXτ−1T1=τ−g2g for 1≤g≤τ−1 and τ≥4. In the following, we will prove that the lemma holds for s=τ. Since Xτ can be merged through a perfect matching by two Xτ−1, namely Xτ−10 and Xτ−11, we discuss the two cases below.Case 1.
H∩Xτ−10≠∅ and H∩Xτ−11≠∅.
LetH1=H−Xτ−11 and H2=H−Xτ−10. Then δH1≥g−1 and δH2≥g−1. Let T2 and T3 be two subgraphs of Xτ−10 and Xτ−11 with T2≅Xg−1 and T3≅Xg−1, respectively. Thus, by the induction hypothesis, we have
(2)NXτH=NXτ−1H1+NXτ−1H2≥NXτ−1T2+NXτ−1T3≥2τ−g+12g−1=τ−g+12g.Then, fors=τ, the lemma holds.Case 2.
H⊆Xτ−10 or H⊆Xτ−11.
Without loss of generality, we suppose thatH⊆Xτ−10. By Lemma 8, we have VH≥2g. Further, by the induction hypothesis, NXτ−1H≥NXτ−1T1=τ−g2g. Then
(3)NXτH=NXτ−1H+VH≥NXτ−1T1+VH≥τ−g2g+2g=τ−g+12g.Hence, the lemma holds.Lemma 13.
For any integerss≥3 and 1≤g≤s−2, κgGEXs,t≤s−g+12g.Proof.
By Definition11, GEXs,t can be decomposed into two disjoint subgraphs L′~ and R′~, where L′~ can be partitioned into 2t subgraphs (clusters) and R′~ can be partitioned into 2s subgraphs (clusters). Without loss of generality, let A⊆VL1′~ such that GEXs,tA≅Xg. Clearly, A=2g. By Definition 7 and Lemma 9, NL1′~A=s−g2g. Further, by Definition 11, each node in VL′~ has a sole neighbor in VR′~. And, for distinct nodes in each Li′~, their neighbors of R′~ lie in different Rj′~. In addition, for any two different subgraphs Li′~ and Lh′~ with i≠h, the edge between them is nonexistent. Thus, each node in L1′~ has exactly one neighbor in GEXs,t−L1′~. Then NGEXs,t−L1′~A=A=2g. Thus, we have
(4)NGEXs,tA=NL1′~A+NGEXs,t−L1′~A=s−g2g+2g=s−g+12g
SinceNGEXs,tA=s−g+12g+2g=s−g+22g and VGEXs,t=2s+t+1>s−g+22g, GEXs,t−NGEXs,tA is disconnected. Then NGEXs,tA is a node-cut of GEXs,t.
In what follows,NGEXs,tA as an Rg-cut of GEXs,t will be proved. That is, δGEXs,t−NGEXs,tA≥g.
SinceGEXs,tA≅Xg, δGEXs,tA=g. By Lemma 9, NL1′~A is an Rg-cut of L1′~, where 1≤g≤s−2. As a result, δL1′~−NL1′~A≥g with 1≤g≤s−2. Moreover, by Definition 11, each node in L1′~ has exactly one neighbor in GEXs,t−L1′~, and for distinct nodes in L1′~, their neighbors in R′~ lie in different Rj′~. Since δGEXs,t=s+1, δGEXs,t−L1′~−NGEXs,t−L1′~A≥s+1−1>g for any node w∈GEXs,t−L1′~−NGEXs,t−L1′~A.
Summary of the above discussion, we haveδGEXs,t−NGEXs,tA≥g. Then NGEXs,tA is a g-good-neighbor cut of GEXs,t. Hence, κgGEXs,t≤s−g+12g with 1≤g≤s−2 and s≥3, the lemma holds.Lemma 16.
For any integerss≥3 and 1≤g≤s−2, κgGEXs,t≥s−g+12g.Proof.
We assumeU as a minimum Rg-cut of GEXs,t. Let U∩VLi′~=ULi′~ and U∩VRj′~=URj′~, where 1≤i≤2t,1≤j≤2s. Then we will show that κgGEXs,t=U≥s−g+12g with 1≤g≤s−2 and s≥3. We consider three cases as follows.Case 1.
Li′~−ULi′~ and Rj′~−URj′~ are connected for each i,j, where 1≤i≤2t,1≤j≤2s.
We prove this case by contradiction. Suppose thatU≤s−g+12g−1. In the following, we will prove that U is not an Rg-cut of GEXs,t.
SinceU is a minimum Rg-cut of GEXs,t, GEXs,t−U is disconnected. In addition, there must exist a component C with C traverses r clusters, where 1≤r≤2s−1. Let Ui=Ci∩U, where Ci be one of these r clusters with 1≤i≤r. As a result, C=⋃i=1rCi−Ui. By Definition 11, for any node in VL′~, it has a sole neighbor in VR′~. And, for distinct nodes in each Li′~, their neighbors of R′~ lie in different Rj′~. In addition, for any two different subgraphs Li′~ and Lh′~ with i≠h, there exists no edge between them. Then there exist at most r−1 cross edges between Ci−Ui and CI−i, where I=1,2,⋯,r. Moreover, there are at least 2s−Ui−r−1 cross edges between Ci−Ui and CJ with J=r+1,r+2,⋯,2s+2t. Clearly, CJ=⋃j=r+12s+2tCj and UJ=⋃j=r+12s+2tUj. Since there is no edge between Ci−Ui and CJ−UJ, UJ≥∑i=1r2s−Ui−r−1. Then, we have
(5)U=U1+U2+⋯+Ur+UJ≥U1+U2+⋯+Ur+∑i=1r2s−Ui−r−1=r2s−r+1.
Letfr=r2s−r+1 with 1≤r≤2s−1. We obtain ∂fr/∂r=2s−2r+1>0. Thus, fr is an increasing function. Therefore, fr≥f1=2s and U≥fr≥2s. In addition, let fg=2s−s−g+12g−1 with 1≤g≤s−2. We obtain that ∂fg/∂g=2ggln2+1−s+1ln2<0. Thus, fg is a decreasing function. Therefore, fg≥fs−2=2s−2+1>0. Then U≥2s>s−g+12g−1, which results in a contradiction with U≤s−g+12g−1.Case 2.
Only one ofLi′~−ULi′~ and Rj′~−URj′~ is disconnected, where 1≤i≤2t,1≤j≤2s.
Without loss generality, assume thatL1′~−UL1′~ is disconnected. Since U is an Rg-cut of GEXs,t, δL1′~−UL1′~≥g−1. Then UL1′~ is a g−1-good-neighbor cut of GEXs,t. By Lemma 9, UL1′~≥s−g+12g−1. By contradiction, suppose that U≤s−g+12g−1 with 1≤g≤s−2 and s≥3. Let UL1′~=U1 and UI=⋃i=22s+2tUi. Then UI=U−U1≤s−g+12g−1−1.
Assume thatGEXs,t−L1′~−UI is disconnected. Then there must exist a component C such that C traverses r clusters, where 1≤r≤2s−1−1. Let Ci be one of these r clusters for 2≤i≤r+1 and Ui=Ci∩U. As a result, C=⋃i=2r+1Ci−Ui. By Definition 11, for any node in VL′~, it has a sole neighbor in VR′~. And for distinct nodes in each Li′~, their neighbors of R′~ lie in different Rj′~. In addition, for any two different subgraphs Li′~ and Lh′~ with i≠h, the edge between them is nonexistent. Then there exist at most r cross edges between Ci−Ui and CI′−i, where I′=1,2,⋯,r,r+1. Moreover, there are at least 2s−Ui−r cross edges between Ci−Ui and CJ with J=r+2,r+3,⋯,2s+2t. Clearly, CJ=⋃j=r+22s+2tCj and UJ=⋃j=r+22s+2tUj. Since there is no edge between Ci−Ui and CJ−UJ, UJ≥∑i=2r+12s−Ui−r. Figure 4 shows an illustration for this case. Then, we have
(6)UI=U2+⋯+Ur+1+UJ≥U2+⋯+Ur+1+∑i=2r+12s−Ui−r=r2s−r.
Letfr=r2s−r with 1≤r≤2s−1−1. We obtain that ∂fr/∂r=2s−2r>0. Thus, fr is an increasing function. Therefore, fr≥f1=2s−1. And UI≥fr≥2s−1. In addition, let fg=2s−1−s−g+12g−1−1 with 1≤g≤s−2 and s≥3. We get that ∂fg/∂g=2g−1gln2+1−s+1ln2<0. Thus, fg is a decreasing function. Therefore, fg≥fs−2>0. Then UI≥2s−1>s−g+12g−1−1, which results in a contradiction with UI≤s−g+12g−1−1.
Thus,GEXs,t−L1′~−UI is connected. Since L1′~−U1 is disconnected, there must exists a component H in L1′~−U1 such that there is no edge between H and GEXs,t−L1′~−UI. Then UI≥VH. Since NL1′~H⊆U1, U=U1+UI≥NL1′~H+VH=NL1′~H. Moreover, since U is an Rg-cut of GEXs,t, δH≥g. By Lemma 8 and L1′~≅Xs, we have U=NL1′~H≥s−g+12g, which results in a contradiction with U≤s−g+12g−1.Case 3.
For any integers1≤i≤2t, 1≤j≤2s, there are at least two of Li′~−ULi′~ and Rj′~−URj′~ that are disconnected.
Without loss of generality, suppose thatL1′~−UL1′~ and L2′~−UL2′~ are disconnected. Since U is an Rg-cut of GEXs,t and by Definition 11, we have δL1′~−UL1′~≥g−1 and δL2′~−UL2′~≥g−1. Then UL1′~ and UL2′~ are two g−1-good-neighbor cuts of GEXs,t. By Lemma 9, UL1′~≥s−g+12g−1 and UL2′~≥s−g+12g−1. Then
(7)U≥UL1′~+UL2′~≥s−g+12g−1+s−g+12g−1=s−g+12g.
Thus,κgGEXs,t=U≥s−g+12g.
Hence, the lemma holds.
Combining Lemma13 and Lemma 16, the following theorem holds.Theorem 14.
For any integerss≥3and1≤g≤s−2, κgGEXs,t=s−g+12g.Figure 4
An illustration for Case2 of Lemma 16.


## 4. Theg-Good-Neighbor Conditional Diagnosability of GEXs,t

In this section, we will determine theg-GNCD of GEXs,t under the PMC model and MM∗ model, respectively, where 1≤g≤s−2.Theorem 15.
For any integerss≥3 and 1≤g≤s−2, tgPGEXs,t=s−g+22g−1.Proof.
First, we show thattgPGEXs,t≤s−g+22g−1 with 1≤g≤s−2 and s≥3. Let A⊆VC1 with C1≅Xs such that GEXs,tA≅Xg. Clearly, A=2g. Suppose that F1^=NGEXs,tA and F2^=NGEXs,tA. By Lemma 13, we have F1^=NGEXs,tA=s−g+12g, and F2^=NGEXs,tA=s−g+22g, where δGEXs,t−F2^≥g. Since δGEXs,t−F1^≥g and δGEXs,t−F2^≥g, F1^ and F2^ are two g-GNCF sets of GEXs,t with F1^≤s−g+22g and F2^≤s−g+22g. On the other hand, since VA=F1^△F2^ and NGEXs,tA=F1^, there is no edge between F1^△F2^ and GEXs,t−F1^∪F2^. By Lemma 4, F1^ and F2^ are indistinguishable under the PMC model. By Definition 6 (2), GEXs,t is not g-good-neighbor conditional s−g+22g-diagnosable under the PMC model. That is, tgPGEXs,t≤s−g+22g−1 for 1≤g≤s−2.
Next, we prove thattgPGEXs,t≥s−g+22g−1 with 1≤g≤s−2 and s≥3. We suppose, to the contrary, that tgPGEXs,t≤s−g+22g−2 for 1≤g≤s−2. And assume that there are two indistinguishable g-GNCF sets F1^ and F2^ with F1^≤s−g+22g−1 and F2^≤s−g+22g−1. In what follows, we consider two cases.Case 1.
VGEXs,t=F1^∪F2^.
Sinces≤t, by Definition 11, we have VGEXs,t=2s+t+1≥22s+1.
SinceF1^∪F2^≤F1^+F2^≤2s−g+22g−1, we have
(8)VGEXs,t−F1^∪F2^≥22s+1−2s−g+22g−1.
Letfg=22s+1−s−g+22g+1+2 with 1≤g≤s−2 and s≥3. We obtain that ∂fg/∂g=g−s−2ln2+12g+1<0. Thus, fg is a decreasing function. Therefore, for 1≤g≤s−2 and s≥3,
(9)fg≥fs−2=22s+1−2s+1+2>0,which induces a contradiction since VGEXs,t=F1^∪F2^.Case 2.
VGEXs,t≠F1^∪F2^.
SinceF1^≠F2^, we may assume that F2^−F1^≠∅. There exists no edge between VGEXs,t−F1^∪F2^ and F1^ΔF2^ because F1^ and F2^ are indistinguishable. Moreover, since F1^ is a g-good-neighbor conditional faulty set, it is easy to verify that δGEXs,tF2^−F1^≥g. By Lemma 8, F2^−F1^≥2g. On the other hand, since both F1^ and F2^ are g-GNCF sets, F1^∩F2^ is also a g-good-neighbor conditional faulty set. Moreover, there is no edge between VGEXs,t−F1^∪F2^ and F1^ΔF2^; thus, GEXs,t−F1^∩F2^ is disconnected. Then F1^∩F2^ is an Rg-cut of GEXs,t. By Theorem 14, F1^∩F2^≥s−g+12g with s≥3 and 1≤g≤s−2. Hence,
(10)F2^=F2^−F1^+F1^∩F2^≥2g+s−g+12g=s−g+22g,which results in a contradiction since F2^≤s−g+22g−1.
To sum up, we can conclude thattgPGEXs,t≥s−g+22g−1 for any integers 1≤g≤s−2 and s≥3.
Hence, the theorem holds.Theorem 24.
For any integers1≤g≤s−2 and s≥4, tgMGEXs,t=s−g+22g−1.Proof.
The proof oftgMGEXs,t≤s−g+22g−1 with 1≤g≤s−2 and s≥4 is similar to Theorem 15, so it is omitted.
Next, we prove thattgMGEXs,t≥s−g+22g−1 with s≥4 and 1≤g≤s−2. We suppose, to the contrary, that tgMGEXs,t≤s−g+22g−2 with s≥4 and 1≤g≤s−2. Moreover, we assume that there are two indistinguishable g-GNCF sets F1^ and F2^, where F1^≤s−g+22g−1 and F2^≤s−g+22g−1.
Sinces≤t, by Definition 11, we have VGEXs,t=2s+t+1≥22s+1.
Furthermore, it is easy to get thatF1^∪F2^≤F1^+F2^≤2s−g+22g−1. Then, we have
(11)VGEXs,t−F1^∪F2^≥22s+1−2s−g+22g−1.
Letfg=22s+1−s−g+22g+1+2 with s≥4 and 1≤g≤s−2. We obtain that ∂fg/∂g=gln2+1−s+2ln22g+1<0. Thus, fg is a decreasing function. Therefore, for s≥4 and 1≤g≤s−2,
(12)fg≥fs−2=22s+1−2s+1+2>0,which results in a contradiction since F2^≤s−g+22g−1.Thus,VGEXs,t≠F1^∪F2^. In addition, an important claim is given as follows.Claim 25.
GEXs,t−F1^∪F2^ has no isolated node.
By contradiction, suppose thatGEXs,t−F1^∪F2^ has at least one isolated node. Then, we prove that the two cases both contradict the supposition.Case 1.
g=1.
SinceF1^≠F2^, without loss of generality, we suppose that F2^−F1^≠∅. When F1^⊂F2^, since F2^ is a 1-GNCF set, GEXs,t−F1^∪F2^ has no isolated node. Now, we consider F1^⊈F2^. The given W is the set of all isolated nodes and B=GEXs,tVGEXs,t−F1^∪F2^−W. Since F1^ is a 1-GNCF set, NGEXs,t−F1^w≥1 for any w∈W.
SinceF1^ and F2^ are indistinguishable, there exists at most one node u∈F2^−F1^ with u is adjacent to w by Lemma 5. Thereby, there exists only one node u∈F2^−F1^ with u adjacent to w. It is easy to see that there is only one node v∈F1^−F2^ with v adjacent to w. Since ΔGEXs,t=t+1, there are at most t−1 neighbors of w in F1^∩F2^ with any isolated node w∈W. Since F2^≤s−g+22g−1 and g=1, F2^≤2s+1. Hence,
(13)∑w∈WNGEXs,tF1^∩F2^w≤Wt−1≤∑x∈F1^∩F2^degGEXs,tx≤F1^∩F2^t+1≤F2^−1t+1≤2st+1.
It follows thatW≤2st+1/t−1≤4s. Thus,
(14)F1^∪F2^+W=F1^+F2^−F1^∩F2^+W≤22s+1−s−1+W≤7s+3.
Letfs=22s−7s−3. We can deduce that ∂fs/∂s>0. Then fs is an increasing function. Therefore, fs≥f4>0, a contradiction. Thus, VB≠∅.
Since the fault-pairF1^,F2^ does not satisfy Lemma 5 and any node in VB is not isolated, there exists no edge between VB and F1^△F2^. Moreover, F1^∩F2^ is also a 1-GNCF set. Thus, F1^∩F2^ is an R1-cut of GEXs,t. By Theorem 14, F1^∩F2^≥2s. Since F1^≤2s+1, F2^≤2s+1, and F1^≠F2^, F1^−F2^=F2^−F1^=1. Let F1^−F2^=v and F2^−F1^=u. Then NGEXs,tF1^−F2^w=NGEXs,tF2^−F1^w=1. Hence, we have v,w∈EGEXs,t and u,w∈EGEXs,t for any isolated node w∈W. By Lemma 10, there are at most two common neighbors between any two nodes in VXs. In addition, by Definition 11, any two cross edges have no common end node. Then we deduce that any two nodes in VGEXs,t have at most two common neighbors. Thus, W≤2. Since there is no common node between any two cross edges and Xs is triangle-free, GEXs,t is triangle-free. Thereby,
(15)F1^∩F2^≥NGEXs,tv−W+NGEXs,tw−u,v+NGEXs,tv−W−2−W≥2s+1−W+s−1−2+W=3s−1−W≥3s−3.
Therefor, fors≥4, we have
(16)F2^=F2^−F1^+F1^∩F2^≥1+3s−3=3s−2>2s+1,which results in a contradiction since F2^≤2s+1.Case 2.
g≥2.
Without loss of generality, we suppose thatF2^−F1^≠∅. Since F1^ is a g-GNCF set of GEXs,t, NGEXs,t−F1^x≥g with any node x∈VGEXs,t−F1^. For any w∈VGEXs,t−F1^∪F2^, there exists at most one neighbor in F2^−F1^ because the fault-pair F1^,F2^ is indistinguishable by Lemma 5. Therefore, NGEXs,t−F1^∪F2^w≥g−1≥1. Since w∈VGEXs,t−F1^∪F2^ is arbitrary, every node of GEXs,t−F1^∪F2^ is not an isolated one.
To sum up, Claim25 holds.
Since there exists no isolated node inGEXs,t−F1^∪F2^ by Claim 25 we have, for any w∈GEXs,t−F1^∪F2^, there exists some node v∈GEXs,t−F1^∪F2^ such that w,v∈EGEXs,t. If u,w∈EGEXs,t for any u∈F1^ΔF2^, u,vw satisfies condition in Lemma 5. Therefore, the g-GNCF sets F1^ and F2^ are distinguishable, which results in a contradiction. By the arbitrariness of w∈GEXs,t−F1^∪F2^, there exists no edge between VGEXs,t−F1^∪F2^ and F1^△F2^.
SinceF1^ is a g-GNCF set and F2^−F1^≠∅, δGEXs,tF2^−F1^≥g. Thus, F2^−F1^≥g+1. Since F1^ and F2^ are both g-GNCF sets and there exists no edge between VGEXs,t−F1^∪F2^ and F1^△F2^, F1^∩F2^ is also an Rg-cut of GEXs,t. By Theorem 14, F1^∩F2^≥s−g+12g. Then F2^=F2^−F1^+F1^∩F2^≥s−g+12g+2g=s−g+22g, which contradicts with F2^≤s−g+22g−1.
Thus,tgMGEXs,t≥s−g+22g−1 for any integers 1≤g≤s−2 and s≥4.
Hence, the proof of theorem is completed.


## 5. Applications to a Family of Famous Networks

In Section2, the definition of the generalized exchanged X-cube GEXs,t has been given. Furthermore, we determine the Rg-connectivity and g-GNCD of GEXs,t in Section 3 and Section 4, respectively. Applying the theorems of Section 3 and Section 4, we can directly establish the Rg-connectivity and g-GNCD of some generalized exchanged X-cubes, including generalized exchanged hypercubes, dual-cube-like networks, generalized exchanged crossed cubes, and locally generalized exchanged twisted cubes. In this section, we will give the applications to these networks.


### 5.1. The Generalized Exchanged Hypercube

In 2005, Loh et al. [36] proposed the exchanged hypercube, which obtained by removing edges from a hypercube Hs+t+1. We denote Ir=1,2,⋯,r, where r is a given position integer. For each n∈Ir, the sequence xrxr−1⋯x1 is a binary string of length r if xn∈0,1. The definition of exchanged hypercubes is presented as follows.Definition 16 (see [36]).
Lets,t≥1, the exchanged hypercube EHs,t consists of the node set VEHs,t and the edge set EEHs,t, two nodes u=us+t⋯ut+1ut⋯u1u0 and v=vs+t⋯vt+1vt⋯v1v0 are linked by an edge, called r-dimensional edge, if and only if the following conditions are satisfied:
(i)
u and v differ exactly in one bit on the r-th bit or on the last bit(ii)
ifr∈It, then u0=v0=1(iii)
r∈Is+t−It, then u0=v0=0.The generalized exchange hypercube was proposed by Cheng et al. [37]. Let s,t≥1, the generalized exchanged hypercube GEHs,t,f consists of two classes of hypercubes: one class contains 2tHs’s, referred to as the Class-0 clusters; and the other contains 2sHt’s, referred to as the Class-1 clusters. Class-0 and Class-1 clusters will be referred to as clusters of opposite class of each other, same class otherwise. The function f is a bijection between nodes of Class-0 clusters and those of Class-1 clusters; for two nodes u,v in the same cluster, fu and fv are in two different clusters, and the edge u,fu is a cross edge. The bijection f ensures the existence of a perfect matching between nodes of Class-0 clusters and those in the Class-1 clusters but ignores the specifics of the perfect matching. Hence, we present the following proposition.Proposition 17.
GEHs,t can be decomposed into two subgraphs L′~ and R′~. Further, L′~ can be partitioned into 2t subgraphs, denoted by Li′~ for i=1,2,⋯,2t. Similarly, R′~ can be partitioned into 2s subgraphs, denoted by Rj′~ for j=1,2,⋯,2s. And GEHs,t satisfies the following conditions (Figure 5 shows the GEH1,1 and GEH1,2):
(a)
For anyi,j, Li′~≅Hs and Rj′~≅Ht. Further, VLi′~=2s and VRj′~=2t(b)
Each node inVL′~ has a sole neighbor in VR′~ and vice versa. In addition, for distinct nodes in each Li′~, their neighbors of R′~ lie in different Rj′~(c)
For any two different subgraphsLi′~ and Lh′~ with i≠h, there exists no edge between them. Similar for Rj′~ and Rk′~ with j≠k.Figure 5
(a)GEH1,1, (b) GEH1,2.
(a)(b)The dual-cube is a special case of the exchanged hypercube whens=t, proposed by Li and Peng [38]. That is, EHn,n≅Dn. The dual-cube-like network DCn[39], which is a generalization of dual-cubes, is isomorphic to EHn−1,n−1, a special case of GEHn−1,n−1 (see DC3 in Figure 6).Figure 6
The dual-cube-like networkDC3.By Proposition17, the generalized exchanged hypercube GEHs,t is the member of generalized exchanged X-cubes, where the X-cube is a hypercube. Then, the following theorems hold obviously.Theorem 18.
(1)
For any integers1≤g≤s−2 and 3≤s≤t, κgGEHs,t=s−g+12g(2)
For any integers1≤g≤n−3 and n≥4, κgDCn=n−g2g.Theorem 19.
(1)
For any integers1≤g≤s−2 and 3≤s≤t, tgPGEHs,t=s−g+22g−1(2)
For any integers1≤g≤n−3 and n≥4, tgPDCn=n−g+12g−1.Theorem 20.
(1)
For any integers1≤g≤s−2 and 4≤s≤t, tgMGEHs,t=s−g+22g−1(2)
For any integers1≤g≤n−3 and n≥5, tgMDCn=n−g+12g−1.


### 5.2. The Generalized Exchanged Crossed Cube

Li et al. [26] give the definition of ECQs,t, which is obtained by removing edges from a crossed cube CQs+t+1. In what follows, we review the definition of exchanged crossed cubes.Definition 21 (see [26]).
Thes,t-dimensional exchanged crossed cube is defined as a graph ECQs,t=GVECQs,t,EECQs,t for s,t≥1, The node set VECQs,t=as−1⋯a0bt−1⋯b0caj,bi,c∈0,1, where 0≤i≤t−1 and 0≤j≤s−1. The edge set EECQs,t consisting of three types of disjoint sets E1, E2, and E3 is shown as follows.
E1:u0≠v0,u⊕v=1, where ⊕ is the exclusive-OR operator.
E2:us+t:t+1=vs+t:t+1,u0=v0=1, ut:1is denoted byb=bt−1⋯b0andvt:1is denoted byb′=b′t−1⋯b′0. Anduandvare adjacent by the following rule: for any integert≥1, if and only if there is anl1≤l≤twithbt−1⋯bl= b′t−1⋯b′l; bl−1≠b′l−1,bl−2=b′l−2iflis even;b2i+1b2i∼b′2i+1b′2i, where0≤i<l−1/2
E3:ut:1=vt:1,u0=v0=0, us+t:t+1is denoted bya=as−1⋯a0andys+t:t+1is denoted bya′=a′t−1⋯a′0. Anduandvare adjacent by the following rule: for any integers≥1, if and only if there is anl1≤l≤swithas−1⋯al= a′s−1⋯a′l;al−1≠a′l−1,al−2=a′l−2iflis even;a2i+1a2i∼a′2i+1a′2i, where0≤i<l−1/2.
xu:vis the bit pattern ofxfrom dimensionuto dimensionv.Lets,t≥1, the generalized crossed cube GECQs,t,f comprises two classes of crossed cubes, referred to as the Class-0 clusters and the Class-1 clusters, respectively. The Class-0 clusters contain 2tCQs’s and the Class-1 clusters contain 2sCQt’s. They will be referred to as clusters of opposite class of each other, same class otherwise. The function f is a bijection between nodes of Class-0 clusters and those of Class-1 clusters such that, for u,v, two nodes of the same cluster, fu and fv, are in two different clusters, and the edge u,fu is a cross edge. The bijection f ensures the existence of a perfect matching between two nodes in different clusters, but there is no requirement for the specifics of the perfect matching. Therefore, we have the following proposition.Proposition 22.
GECQs,t can be decomposed into two disjoint subgraphs L′~ and R′~. And L′~ and R′~ are the subgraphs induced by VL′~ and VR′~, respectively, where
(17)VL′~=as−1as−2⋯a0bt−1⋯b00aj,bi∈0,1,with 0≤j≤s−1 and 0≤i≤t−1.
(18)VR′~=as−1as−2⋯a0bt−1⋯b01aj,bi∈0,1,with 0≤j≤s−1 and 0≤i≤t−1.By Definition21, L′~ can be partitioned into 2t subgraphs, denoted by Li′~ such that for v1, v2∈Li′~, v1t:1=v2t:1, where i=1,2,⋯,2t. Similarly, R′~ can be partitioned into 2s subgraphs, denoted by Rj′~ such that w1, w2∈Rj′~, w1t+1:s+t=w2t+1:s+t, for j=1,2,⋯,2s. And GECQs,t satisfies the following conditions (see GECQ1,3 in Figure 7):
(1)
For anyi,j, Li′~≅CQs and Rj′~≅CQt. Further, VLi′~=2s and VRj′~=2t(2)
Each node inVL′~ has a sole neighbor in VR′~ and vice versa. In addition, for distinct nodes in each Li′~, their neighbors of R′~ lie in different Rj′~(3)
For any two different subgraphsLi′~ and Lh′~ with i≠h, there exists no edge between them. Similar for Rj′~ and Rk′~ with j≠k.Figure 7
An exchanged crossed cubeGECQ1,3.By Proposition22, the exchanged crossed cube GECQs,t is an exchanged X-cube, where the X-cube is a crossed cube. Then, the following theorems hold obviously.Theorem 23.
For any integers1≤g≤s−2 and 3≤s≤t, κgGECQs,t=s−g+12g.Theorem 24.
(1)
For any integers1≤g≤s−2 and 3≤s≤t, tgPGECQs,t=s−g+22g−1(2)
For any integers1≤g≤s−2 and 4≤s≤t, tgMGECQs,t=s−g+22g−1.


### 5.3. The Locally Generalized Exchanged Twisted Cube

The locally exchanged twisted cube proposed by Chang et al. [29], obtained by removing edges from a locally twisted cube LTQs+t+1. The definition of locally exchanged twisted cube is introduced as follows.Definition 25 (see [29]).
Thes,t-dimensional locally exchanged twisted cube is defined as a graph LETQs,t=GVLETQs,t,ELETQs,t for s,t≥1, The node set VLETQs,t=x=xt+s⋯xt+1xt⋯x1x0:xi∈0,1with0≤i≤t+s. ELETQs,t is the edge set consisting of the following three types of disjoint sets E1, E2, and E3.
(19)E1=x,y∈V×V:x⊕y=20E2=x,y∈V×V:x0=y0=1,x1=y1=0andx⊕y=2kfork∈3,t∪x,y∈V×V:x0=y0=x1=y1=1andx⊕y=2k+2k−1fork∈3,t∪x,y∈V×V:x0=y0=1andx⊕y∈21,22E3=x,y∈V×V:x0=y0=xt+1=yt+1=0andx⊕y=2kfork∈t+3,t+s∪x,y∈V×V:x0=y0=0,xt+1=yt+1=1andx⊕y=2k+2k−1fork∈t+3,t+s∪x,y∈V×V:x0=y0=0andx⊕y∈2t+1,2t+2Lets,t≥1; there are two classes of locally twisted cubes in the locally generalized exchanged twisted cube LGETQs,t,f: one class, referred to as the Class-0 clusters, contains 2tLTQs’s; and the other, referred to as the Class-1 clusters, contains 2sLTQt’s. They will be referred to as clusters of opposite class of each other, same class otherwise. There exists a bijection function f between nodes of Class-0 clusters and those of Class-1 clusters. For two nodes u,v in the same cluster, fu and fv belong to two different ones, and the edge u,fu is a cross edge. The bijection f ensures the existence of a perfect matching between nodes of Class-0 clusters and those in the Class-1 clusters, but the specifics of the perfect matching can be ignored. Further, we obtain the proposition as follows.Proposition 26.
LGETQs,t can be decomposed into two disjoint subgraphs L′~ and R′~. L′~ can be partitioned into 2t subgraphs, denoted by Li′~ for i=1,2,⋯,2t. Similarly, R′~ can be partitioned into 2s subgraphs, denoted by Rj′~ for j=1,2,⋯,2s. And LGETQs,t satisfies the following conditions (see LGETQ1,3 in Figure 8):
(a)
For anyi,j, Li′~≅LTQs and Rj′~≅LTQt. Further, VLi′~=2s and VRj′~=2t(b)
Each node inVL′~ has a sole neighbor in VR′~ and vice versa. In addition, for distinct nodes in each Li′~, their neighbors of R′~ lie in different Rj′~(c)
For any two different subgraphsLi′~ and Lh′~ with i≠h, there exits no edge connects them. Similar for Rj′~ and Rk′~ with j≠k.Figure 8
A locally exchanged twisted cubeLGETQ1,3.By Proposition26, the locally exchanged twisted cube LGETQs,t is a member of generalized exchanged X-cubes, where the X-cube is a locally twisted cube. Then, we have the following theorems.Theorem 27.
(1)
For any integers1≤g≤s−2 and 3≤s≤t, κgLGETQs,t=s−g+12g(2)
For any integers1≤g≤s−2 and 3≤s≤t, tgPLGETQs,t=s−g+22g−1(3)
For any integers1≤g≤s−2 and 4≤s≤t, tgMLGETQs,t=s−g+22g−1.


## 5.1. The Generalized Exchanged Hypercube

In 2005, Loh et al. [36] proposed the exchanged hypercube, which obtained by removing edges from a hypercube Hs+t+1. We denote Ir=1,2,⋯,r, where r is a given position integer. For each n∈Ir, the sequence xrxr−1⋯x1 is a binary string of length r if xn∈0,1. The definition of exchanged hypercubes is presented as follows.Definition 16 (see [36]).
Lets,t≥1, the exchanged hypercube EHs,t consists of the node set VEHs,t and the edge set EEHs,t, two nodes u=us+t⋯ut+1ut⋯u1u0 and v=vs+t⋯vt+1vt⋯v1v0 are linked by an edge, called r-dimensional edge, if and only if the following conditions are satisfied:
(i)
u and v differ exactly in one bit on the r-th bit or on the last bit(ii)
ifr∈It, then u0=v0=1(iii)
r∈Is+t−It, then u0=v0=0.The generalized exchange hypercube was proposed by Cheng et al. [37]. Let s,t≥1, the generalized exchanged hypercube GEHs,t,f consists of two classes of hypercubes: one class contains 2tHs’s, referred to as the Class-0 clusters; and the other contains 2sHt’s, referred to as the Class-1 clusters. Class-0 and Class-1 clusters will be referred to as clusters of opposite class of each other, same class otherwise. The function f is a bijection between nodes of Class-0 clusters and those of Class-1 clusters; for two nodes u,v in the same cluster, fu and fv are in two different clusters, and the edge u,fu is a cross edge. The bijection f ensures the existence of a perfect matching between nodes of Class-0 clusters and those in the Class-1 clusters but ignores the specifics of the perfect matching. Hence, we present the following proposition.Proposition 17.
GEHs,t can be decomposed into two subgraphs L′~ and R′~. Further, L′~ can be partitioned into 2t subgraphs, denoted by Li′~ for i=1,2,⋯,2t. Similarly, R′~ can be partitioned into 2s subgraphs, denoted by Rj′~ for j=1,2,⋯,2s. And GEHs,t satisfies the following conditions (Figure 5 shows the GEH1,1 and GEH1,2):
(a)
For anyi,j, Li′~≅Hs and Rj′~≅Ht. Further, VLi′~=2s and VRj′~=2t(b)
Each node inVL′~ has a sole neighbor in VR′~ and vice versa. In addition, for distinct nodes in each Li′~, their neighbors of R′~ lie in different Rj′~(c)
For any two different subgraphsLi′~ and Lh′~ with i≠h, there exists no edge between them. Similar for Rj′~ and Rk′~ with j≠k.Figure 5
(a)GEH1,1, (b) GEH1,2.
(a)(b)The dual-cube is a special case of the exchanged hypercube whens=t, proposed by Li and Peng [38]. That is, EHn,n≅Dn. The dual-cube-like network DCn[39], which is a generalization of dual-cubes, is isomorphic to EHn−1,n−1, a special case of GEHn−1,n−1 (see DC3 in Figure 6).Figure 6
The dual-cube-like networkDC3.By Proposition17, the generalized exchanged hypercube GEHs,t is the member of generalized exchanged X-cubes, where the X-cube is a hypercube. Then, the following theorems hold obviously.Theorem 18.
(1)
For any integers1≤g≤s−2 and 3≤s≤t, κgGEHs,t=s−g+12g(2)
For any integers1≤g≤n−3 and n≥4, κgDCn=n−g2g.Theorem 19.
(1)
For any integers1≤g≤s−2 and 3≤s≤t, tgPGEHs,t=s−g+22g−1(2)
For any integers1≤g≤n−3 and n≥4, tgPDCn=n−g+12g−1.Theorem 20.
(1)
For any integers1≤g≤s−2 and 4≤s≤t, tgMGEHs,t=s−g+22g−1(2)
For any integers1≤g≤n−3 and n≥5, tgMDCn=n−g+12g−1.


## 5.2. The Generalized Exchanged Crossed Cube

Li et al. [26] give the definition of ECQs,t, which is obtained by removing edges from a crossed cube CQs+t+1. In what follows, we review the definition of exchanged crossed cubes.Definition 21 (see [26]).
Thes,t-dimensional exchanged crossed cube is defined as a graph ECQs,t=GVECQs,t,EECQs,t for s,t≥1, The node set VECQs,t=as−1⋯a0bt−1⋯b0caj,bi,c∈0,1, where 0≤i≤t−1 and 0≤j≤s−1. The edge set EECQs,t consisting of three types of disjoint sets E1, E2, and E3 is shown as follows.
E1:u0≠v0,u⊕v=1, where ⊕ is the exclusive-OR operator.
E2:us+t:t+1=vs+t:t+1,u0=v0=1, ut:1is denoted byb=bt−1⋯b0andvt:1is denoted byb′=b′t−1⋯b′0. Anduandvare adjacent by the following rule: for any integert≥1, if and only if there is anl1≤l≤twithbt−1⋯bl= b′t−1⋯b′l; bl−1≠b′l−1,bl−2=b′l−2iflis even;b2i+1b2i∼b′2i+1b′2i, where0≤i<l−1/2
E3:ut:1=vt:1,u0=v0=0, us+t:t+1is denoted bya=as−1⋯a0andys+t:t+1is denoted bya′=a′t−1⋯a′0. Anduandvare adjacent by the following rule: for any integers≥1, if and only if there is anl1≤l≤swithas−1⋯al= a′s−1⋯a′l;al−1≠a′l−1,al−2=a′l−2iflis even;a2i+1a2i∼a′2i+1a′2i, where0≤i<l−1/2.
xu:vis the bit pattern ofxfrom dimensionuto dimensionv.Lets,t≥1, the generalized crossed cube GECQs,t,f comprises two classes of crossed cubes, referred to as the Class-0 clusters and the Class-1 clusters, respectively. The Class-0 clusters contain 2tCQs’s and the Class-1 clusters contain 2sCQt’s. They will be referred to as clusters of opposite class of each other, same class otherwise. The function f is a bijection between nodes of Class-0 clusters and those of Class-1 clusters such that, for u,v, two nodes of the same cluster, fu and fv, are in two different clusters, and the edge u,fu is a cross edge. The bijection f ensures the existence of a perfect matching between two nodes in different clusters, but there is no requirement for the specifics of the perfect matching. Therefore, we have the following proposition.Proposition 22.
GECQs,t can be decomposed into two disjoint subgraphs L′~ and R′~. And L′~ and R′~ are the subgraphs induced by VL′~ and VR′~, respectively, where
(17)VL′~=as−1as−2⋯a0bt−1⋯b00aj,bi∈0,1,with 0≤j≤s−1 and 0≤i≤t−1.
(18)VR′~=as−1as−2⋯a0bt−1⋯b01aj,bi∈0,1,with 0≤j≤s−1 and 0≤i≤t−1.By Definition21, L′~ can be partitioned into 2t subgraphs, denoted by Li′~ such that for v1, v2∈Li′~, v1t:1=v2t:1, where i=1,2,⋯,2t. Similarly, R′~ can be partitioned into 2s subgraphs, denoted by Rj′~ such that w1, w2∈Rj′~, w1t+1:s+t=w2t+1:s+t, for j=1,2,⋯,2s. And GECQs,t satisfies the following conditions (see GECQ1,3 in Figure 7):
(1)
For anyi,j, Li′~≅CQs and Rj′~≅CQt. Further, VLi′~=2s and VRj′~=2t(2)
Each node inVL′~ has a sole neighbor in VR′~ and vice versa. In addition, for distinct nodes in each Li′~, their neighbors of R′~ lie in different Rj′~(3)
For any two different subgraphsLi′~ and Lh′~ with i≠h, there exists no edge between them. Similar for Rj′~ and Rk′~ with j≠k.Figure 7
An exchanged crossed cubeGECQ1,3.By Proposition22, the exchanged crossed cube GECQs,t is an exchanged X-cube, where the X-cube is a crossed cube. Then, the following theorems hold obviously.Theorem 23.
For any integers1≤g≤s−2 and 3≤s≤t, κgGECQs,t=s−g+12g.Theorem 24.
(1)
For any integers1≤g≤s−2 and 3≤s≤t, tgPGECQs,t=s−g+22g−1(2)
For any integers1≤g≤s−2 and 4≤s≤t, tgMGECQs,t=s−g+22g−1.


## 5.3. The Locally Generalized Exchanged Twisted Cube

The locally exchanged twisted cube proposed by Chang et al. [29], obtained by removing edges from a locally twisted cube LTQs+t+1. The definition of locally exchanged twisted cube is introduced as follows.Definition 25 (see [29]).
Thes,t-dimensional locally exchanged twisted cube is defined as a graph LETQs,t=GVLETQs,t,ELETQs,t for s,t≥1, The node set VLETQs,t=x=xt+s⋯xt+1xt⋯x1x0:xi∈0,1with0≤i≤t+s. ELETQs,t is the edge set consisting of the following three types of disjoint sets E1, E2, and E3.
(19)E1=x,y∈V×V:x⊕y=20E2=x,y∈V×V:x0=y0=1,x1=y1=0andx⊕y=2kfork∈3,t∪x,y∈V×V:x0=y0=x1=y1=1andx⊕y=2k+2k−1fork∈3,t∪x,y∈V×V:x0=y0=1andx⊕y∈21,22E3=x,y∈V×V:x0=y0=xt+1=yt+1=0andx⊕y=2kfork∈t+3,t+s∪x,y∈V×V:x0=y0=0,xt+1=yt+1=1andx⊕y=2k+2k−1fork∈t+3,t+s∪x,y∈V×V:x0=y0=0andx⊕y∈2t+1,2t+2Lets,t≥1; there are two classes of locally twisted cubes in the locally generalized exchanged twisted cube LGETQs,t,f: one class, referred to as the Class-0 clusters, contains 2tLTQs’s; and the other, referred to as the Class-1 clusters, contains 2sLTQt’s. They will be referred to as clusters of opposite class of each other, same class otherwise. There exists a bijection function f between nodes of Class-0 clusters and those of Class-1 clusters. For two nodes u,v in the same cluster, fu and fv belong to two different ones, and the edge u,fu is a cross edge. The bijection f ensures the existence of a perfect matching between nodes of Class-0 clusters and those in the Class-1 clusters, but the specifics of the perfect matching can be ignored. Further, we obtain the proposition as follows.Proposition 26.
LGETQs,t can be decomposed into two disjoint subgraphs L′~ and R′~. L′~ can be partitioned into 2t subgraphs, denoted by Li′~ for i=1,2,⋯,2t. Similarly, R′~ can be partitioned into 2s subgraphs, denoted by Rj′~ for j=1,2,⋯,2s. And LGETQs,t satisfies the following conditions (see LGETQ1,3 in Figure 8):
(a)
For anyi,j, Li′~≅LTQs and Rj′~≅LTQt. Further, VLi′~=2s and VRj′~=2t(b)
Each node inVL′~ has a sole neighbor in VR′~ and vice versa. In addition, for distinct nodes in each Li′~, their neighbors of R′~ lie in different Rj′~(c)
For any two different subgraphsLi′~ and Lh′~ with i≠h, there exits no edge connects them. Similar for Rj′~ and Rk′~ with j≠k.Figure 8
A locally exchanged twisted cubeLGETQ1,3.By Proposition26, the locally exchanged twisted cube LGETQs,t is a member of generalized exchanged X-cubes, where the X-cube is a locally twisted cube. Then, we have the following theorems.Theorem 27.
(1)
For any integers1≤g≤s−2 and 3≤s≤t, κgLGETQs,t=s−g+12g(2)
For any integers1≤g≤s−2 and 3≤s≤t, tgPLGETQs,t=s−g+22g−1(3)
For any integers1≤g≤s−2 and 4≤s≤t, tgMLGETQs,t=s−g+22g−1.


## 6. Compare Results

In this section, we will illustrate the advantages ofRg-connectivity and g-GNCD compared to traditional connectivity and traditional diagnosability, respectively. Let us review their definition. The connectivity, which is less than the minimum degree of graph, is the minimum number of nodes that make the graph disconnected. The maximum number of faulty processors that the system can precisely point out is as known as the diagnosability of the system, which is equal to the minimum degree of graph in most cases. The g-good-neighbor conditional connectivity (Rg-connectivity) is the minimum number of nodes that make the graph disconnected, and each node has at least g neighbors in every remaining component. The g-good-neighbor conditional diagnosability (g-GNCD) is the maximum number of faulty processors that can be identified under the condition that every fault-free processor has no less than g fault-free neighbors. We have determined that the Rg-connectivity of GEXs,t is s−g+12g and the g-GNCD of GEXs,t is s−g+22g−1. Figure 9 shows that Rg-connectivity and g-GNCD are both about 2g times the minimum degree of graph. Therefore, we can speculate that Rg-connectivity is about 2g times traditional connectivity and g-GNCD is about 2g times traditional diagnosability, which means that Rg-connectivity and g-GNCD can better evaluate the fault tolerance of network.Figure 9
(a) The minimum degree andRg-connectivity of GEXs,t. (b) The minimum degree and g-GNCD of GEXs,t.
(a)(b)


## 7. Conclusion

TheRg-connectivity and g-GNCD are two significant metrics for reliability of multiprocessor systems. Exchanged X-cubes are a class of irregular networks, obtained by deleting links from hypercubes and some variant networks of hypercubes (X-cubes). They not only combine the advantages of X-cubes but also reduce the interconnection complexity. Exchanged X-cubes classify its nodes into two different classes clusters with a unique connecting rule. In this paper, we propose the generalized exchanged X-cubes framework so that architecture can be constructed by different connecting rules. We first give the definition of a family of generalized exchanged X-cubes, including generalized exchanged hypercubes, dual-cube-like networks, generalized exchanged crossed cubes, and locally exchanged twisted cubes as members. Then we determine the Rg-connectivity and g-GNCD of generalized exchanged X-cubes. Finally, the Rg-connectivity and g-GNCD of generalized exchanged hypercubes, dual-cube-like networks, generalized exchanged crossed cubes, and locally exchanged twisted cubes are established directly. As a future research, we attempt to evaluate the Rg-connectivity and g-GNCD of other generalized exchanged X-cubes using methods extended from the proposed method in this paper.



---

*Source: 9793082-2020-05-26.xml*