<figure><img src="image_1.png" /></figure>

HAL
open science

# Conditional Diagnosability of Complete Josephus Cubes

Lishan Lu, Shuming Zhou

► To cite this version:

Lishan Lu, Shuming Zhou. Conditional Diagnosability of Complete Josephus Cubes. 10th International Conference on Network and Parallel Computing (NPC), Sep 2013, Guiyang, China. pp.220-231, 10.1007/978-3-642-40820-5_19. hal-01513769

HAL Id: hal-01513769

https://inria.hal.science/hal-01513769

Submitted on 25 Apr 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Conditional Diagnosability of Complete
Josephus Cubes

Lishan Lu¹ Shuming Zhou¹,² *

School of Mathematics and Computer Science, Fujian Normal University,
Fuzhou, Fujian, 350007, P.R. China
894729679@qq.com

Key Laboratory of Network Security and Cryptology, Fujian Normal University,
Fuzhou, Fujian, 350007, P.R. China
zhoushuming@fjnu.edu.cn

**Abstract.** The growing size of the multiprocessor system increases its vulnerability to component failures. The fault diagnosis is the process of identifying faulty processors in a system through self-testing, and the diagnosability is an important parameter to measure the reliability of an interconnection network. As a new measure of fault tolerance, conditional diagnosability can better evaluate the real diagnosability of interconnection networks. In this paper, we derive the conditional diagnosability of the multiprocessor systems in terms of Complete Josephus Cubes $CJC_n$ ($n \ge 8$) under the comparison model.

**Key words:** Comparison diagnosis; conditional diagnosability; Complete Josephus Cubes

# 1 Introduction

The process of identifying faulty processors in a system by analyzing the outcomes of available inter-processor tests is called *system-level diagnosis*. The foundation of system diagnosis and an original diagnostic model, namely the PMC model, were established in a classic paper by Preparata et al. [11]. Its target is to identify the exact set of all faulty nodes before their repair or replacement. All tests are performed between two adjacent processors, and it was assumed that a test result is reliable (respectively, unreliable) if the processor that initiates the test is fault-free (respectively, faulty). The comparison-based diagnosis models, first proposed by Malek [9] and Chwa and Hakimi [1], have been considered to be a practical approach for fault diagnosis in multiprocessor systems. In these models, the same job is assigned to a pair of processors in the system and their outputs are compared by a central observer. Sengupta and Dahbura [12] developed this comparison approach such that the comparisons have no central unit involved. Lin et al. [8] introduced the conditional diagnosis under the comparison model. By evaluating the size of connected components, they obtained that

* This work was also partly supported by the Natural Science Foundation of Fujian Province(Nos. 2013J01221, JA12073).
the conditional diagnosability of Star graph $S_n$ is $3n-7$. Additionally, Hsu et al. [4] have proved that the conditional diagnosability of hypercube is $3n-5$. This idea was attributed to Lai et al. [7] who is the first to use a restricted diagnosis strategy. Recently, the conditional diagnosabilities of cross cubes are also obtained [18].

The Josephus Cube [5] is a recently proposed novel interconnection network that has improved topological and exhibits better embedding and communications performance than the Binary Hypercube and several of its variants [18, 20]. Its link-augmented form, Complete Josephus Cubes, can also be applied as node cluster in an optical-based architecture suitable for large-scale hierarchical networks[6]. These clustered networks can offer system upgrade on a node cluster basis, improving overall network scalability. Loh and Hsu described a cost effective fault-tolerant strategy that included a fault-tolerant routing algorithm with supporting routing hardware.

Based on the fault tolerance of the Complete Josephus Cube $CJC_n$, this paper establishes the conditional diagnosability of the Complete Josephus Cube $CJC_n$ ($n \ge 8$) under the comparison diagnosis model. The rest of this paper is organized as follows. Section 2 introduces some definitions, notations and the structure of the Complete Josephus Cube $CJC_n$. Section 3 is devoted to the fault resiliency of $CJC_n$; and Section 4 concentrates on the conditional diagnosability of $CJC_n$. Section 5 concludes the paper.

## 2 Preliminaries

Throughout this paper, we use a graph $G = G(V, E)$ to represent an interconnection network, where each node $u \in V$ denotes a processor and each edge $(u, v) \in E$ denotes a link between nodes $u$ and $v$. Let $S$ be a subset of $V(G)$. The subgraph of $G$ induced by $S$, denoted by $G[S]$, is the graph with the vertex set $S \cap V(G)$ and the edge set $\{(u, v) | (u, v) \in E(G), u, v \in S\}$. For any subset $F \subset V$, the notation $G \setminus F$ (or $G - F$) represents the graph obtained by removing the vertices in $F$ from $G$ and deleting those edges with at least one end vertex in $F$, simultaneously. If $G \setminus F$ is disconnected, $F$ is called a vertex cut or a separating set. The components of $G \setminus F$ are its maximal connected subgraphs. For any node $u$ of $G$, $N(u)$ denotes the set of all its neighboring nodes, i.e., $N(u) = \{v | (u, v) \in E\}$. For any set $F \subset V$, let $N(F) = \bigcup_{u \in F} N(u) - F$, $N[F] = N(F) \cup F$. For brevity, $N[u] = N(u) \cup \{u\}$, $N(\{u, v\})$ and $N[\{u, v\}]$ are written as $N(u, v)$ and $N[u, v]$. The symmetric difference of any two sets $F_1$ and $F_2$ is defined as the set $F_1 \triangle F_2 = (F_1 - F_2) \cup (F_2 - F_1)$.

The $n$-hypercube, denoted by $Q_n$, is a graph with the vertex set $V(Q_n) = \{a_n a_{n-1} \cdots a_1 | a_i \in \{0, 1\}, i \in \{1, 2, \dots, n\}\}$, and the adjacency is defined as follows: A vertex $a_n a_{n-1} \cdots a_1$ is adjacent to the vertex $a_n a_{n-1} \cdots a_{i+1} \bar{a}_i a_{i-1} \cdots a_1$ ($i \in \{1, 2, \dots, n\}$). For any two vertices $x$ and $y$, we use $H(x, y)$ to denote the Hamming distance between $x$ and $y$, which is the number of different positions between the binary strings of $x$ and $y$.
Remark 1. [16,7] Let any subset $S \subset V(Q_n)$ ($n \ge 3$) with $n \le |S| \le 2n-3$. If $Q_n-S$ is not connected, $Q_n-S$ has two components, one of which is trivial, and the other is of size $2^n - |S| - 1$.

<figure><img src="image_3.png" /><figcaption>Figure 1. The Complete Josephus Cubes (a) $CJC_3$ and (b) $CJC_4$</figcaption></figure>

Now, we formally present the structure of the Complete Josephus Cube $CJC_n$.

**Definition 1.** [6] The $n$-dimensional ($n \ge 3$) Complete Josephus Cube, denoted by $CJC_n$, is a graph with the vertex set $V(CJC_n) = \{a_n|a_{n-1}|\cdots|a_1 \mid a_i \in$
$\{0,1\}, i \in \{1,2,...,n\}$, and the adjacency is defined as follows: A vertex $a_n \cdots a_1$ is adjacent to

(1) the vertex $a_n a_{n-1} \cdots a_{i+1} \bar{a}_i a_{i-1} \cdots a_1$, where $i \in \{1,2,...,n\}$;

(2) the vertex $\bar{a}_n \bar{a}_{n-1} \cdots \bar{a}_2 \bar{a}_1$;

(3) the vertex $a_n a_{n-1} \cdots a_3 \bar{a}_2 \bar{a}_1$.

The edges of type (1) are referred to as *Hamming (H) links*, the edges of type (2) are referred to as *complementary (C) links or cross links* and the edges of type (3) are referred to as *Josephus (J) links*. The structures of the $CJC_3$ and $CJC_4$ are shown in Figure 1.

**Definition 2.** [13, 10] The enhanced hypercube, denoted by $EQ_{n,k}$, is a graph with the vertex set $V(EQ_{n,k}) = \{a_n a_{n-1} \cdots a_1 \mid a_i \in \{0,1\}, i \in \{1,2,...,n\}\}$, and the adjacency is defined as follows: A vertex $a_n \cdots a_1$ is adjacent to

(1) the vertex $a_n a_{n-1} \cdots a_{i+1} \bar{a}_i a_{i-1} \cdots a_1$, where $i \in \{1,2,...,n\}$;

(2) the vertex $a_n \cdots a_{k+1} \bar{a}_k \bar{a}_{k-1} \cdots \bar{a}_2 \bar{a}_1$.

If $k=n$, $EQ_{n,k}$ is degrated to the folded cube $FQ_n$ [19].

*Remark 2.* By the definition of the Complete Josephus Cubes, it is easy to see that any *n*-dimensional Complete Josephus Cube $CJC_n$ can be viewed as $L \oplus R$ where *L* (respectively, *R*) is subgraph of $CJC_n$ with the prefix 0 (respectively, 1) of each vertex. And we have $L \cong R \cong EQ_{n-1,2}$. $CJC_n$ has the hypercube $Q_n$, the folded hypercube $FQ_n$ and the enhanced hypercube $EQ_{n,2}$ as its subgraphs.

*Remark 3.* (1) The connectivity of hypercube $Q_n$ is $n$[14];

(2) The connectivity of enhanced hypercube $EQ_{n,k}$ is $n + 1$ (when $k = n$, $EQ_{n,n}$ is Folded cube $FQ_n$)[14];

(3) The restricted vertex connectivity of hypercube $Q_n$ is $2n - 2$[15];

(4) Let $S \subset V(Q_n)$ such that $Q_n - S$ has at least three isolated vertices or an isolated edge and two isolated edges. Then $|S| \ge 3n - 4$[17].

### 3 Fault tolerance of $CJC_n$

The connectivity $\kappa(G)$ of a graph $G = G(V, E)$ is the minimum number of nodes whose removal results in a disconnected or a trivial (one node) graph. A *k*-regular graph is *maximally connected* if it is *k*-connected. A *k*-regular graph is (*loosely*) *super k-connected* if any one of its minimum separating sets is a set of the neighbors of some vertex. In addition, if the deletion of a minimum separating set results in a graph with two components (one of which has only one vertex), then the graph is *tightly super k-connected*. To compensate for this shortcoming, Esfahanian introduced the concepts of the restricted cut and the restricted connectivity of a graph [3]. A restricted vertex set $S$ is a restricted vertex-cut if $G \setminus S$ is disconnected, and no component is an isolated vertex. The restricted vertex connectivity of a graph $G$, denoted by $\kappa'(G)$, is the minimum cardinality of a restricted vertex-cut. It has been shown that if a network possesses the restricted connectivity property, it is more reliable and has the lower vertex failure comparing to that has only the super connectivity property.
**Lemma 1.** Let $G$ be a graph, $u$ and $v$ be any two vertices of $G$ such that $u$ and $v$ have common neighbors. Then we have the following.

(1) If the graph $G$ is hypercube $Q_n$, $|N(u) \cap N(v)| = 2^{[14]}$;

(2) If the graph $G$ is folded cube $FQ_n$, $|N(u) \cap N(v)| = 2^{[20]}$;

(3) If the graph $G$ is augment cube $AQ_n$, $2 \le |N(u) \cap N(v)| \le 4^{[2]}$.

**Lemma 2.** For any integer $n$ with $n \ge 5$, $u$ and $v$ be any two vertices of the Complete Josephus Cube $CJC_n$ such that $u$ and $v$ have common neighbors, $|N(u) \cap N(v)| = 2$.

*Proof.* Let $u = a_n a_{n-1} \dots a_2 a_1$. Since $CJC_n$ has $Q_n$ as its subgraph and $AQ_n$ as its supergraph, by Lemma 1(1)(3), we have $2 \le |N(u) \cap N(v)| \le 4$.

(1) $H(u, v) = 1$.

If $v = a_n a_{n-1} \dots a_2 \bar{a}_1$ or $a_n a_{n-1} \dots a_3 \bar{a}_2 a_1$, $|N(u) \cap N(v)| = 2$; otherwise, $v = a_n a_{n-1} \dots a_{i+1} \bar{a}_i a_{i-1} \dots a_2 a_1$, $|N(u) \cap N(v)| = 0$.

(2) $H(u, v) = 2$.

By the definition of $CJC_n$, $v = a_n a_{n-1} \dots a_{i+1} \bar{a}_i a_{i-1} \dots \bar{a}_2 a_1$ or $a_n a_{n-1} \dots a_{i+1} \bar{a}_i a_{i-1} \dots a_{j+1} \bar{a}_j a_{j-1} \dots a_2 a_1$, the pair of $u$ and $v$ have exactly two common neighbors.

(3) $H(u, v) = 3$.

If $v = a_n a_{n-1} \dots a_{i+1} \bar{a}_i a_{i-1} \dots a_3 \bar{a}_2 \bar{a}_1$, $|N(u) \cap N(v)| = 2$; otherwise, $|N(u) \cap N(v)| = 0$.

(4) $H(u, v) = n - 1$.

If $v = \bar{a}_n \bar{a}_{n-1} \dots \bar{a}_3 a_2 a_1$, $|N(u) \cap N(v)| = 2$; otherwise, $|N(u) \cap N(v)| = 0$.

(5) $4 \le H(u, v) \le n - 3$ or $H(u, v) = n$.

Since there exists no common neighbor of $u$ and $v$, $|N(u) \cap N(v)| = 0$.

From the discussion above, it is easy to see that Lemma 2 holds.

**Lemma 3.** The Complete Josephus Cube $CJC_n$ ($n \ge 4$) is tightly super $n + 2$-connected.

*Proof.* Taking into account that $CJC_n$ has regular degree $n + 2$, we need only to prove that if $CJC_n - S$ is disconnected with $|S| = n + 2$, $CJC_n - S$ has exactly two connected components one of which is an isolated vertex. We denote $S_L = S \cap L$ and $S_R = S \cap R$.

Since $CJC_n - S$ is disconnected, exactly one of $L - S_L$ and $R - S_R$ is disconnected (otherwise, both $L - S_L$ and $R - S_R$ are disconnected, by Remark 3(2), $|S| = |S_L| + |S_R| \ge 2n > n$ for $n \ge 4$, a contraction). Without loss of generality, we assume that $L - S_L$ is disconnected and $R - S_R$ is connected. Then we have $|S_L| \ge n$.

If $|S_R| \le 1$, by the fact that $|N(v) \cap R| = 2$ for any vertex $v \in L - S_L$ and $R - S_R$ is connected, $CJC_n - S$ is connected, a contraction. Therefore, we have $|S_R| = 2$ and $|S_L| = n$.

If there is not isolated vertex in $L - S_L$, let $C$ be arbitrary one connected component of $L - S_L$ with $|C| \ge 2$, then $C$ is connected to $R - S_R$ (in detail, $|N(C) \cap R| \ge 3 > |S_R|$, which means that $CJC_n - S$ is connected, a contraction).
If there are at least two isolated vertices in $L - S_L$, let $v_1$ and $v_2$ be any two isolated vertices of $L - S_L$, by Lemma 2, we have

$$ 
\begin{aligned}
|N_L(v_1) \cup N_L(v_2)| &= |N_L(v_1)| + |N_L(v_2)| - |N_L(v_1) \cap N_L(v_2)| \\
&= n + n - 2 \\
&> |S|,
\end{aligned}
$$

a contradiction.

By the discussion above, there is exactly one isolated vertex say $v$, in $L - S_L$ and $N_L(v) = S_L$. Let $C$ be arbitrary one connected component of $L - S_L - \{v\}$ with $|C| \ge 2$, then $C$ is connected to $R - S_R$ (in detail, $|N(C) \cap R| \ge 3 > |S_R|$), which means that $(L - S_L - \{v\}) \cup (R - S_R)$ is connected. In addition, $N(v) \cap R = S_R$ (otherwise, $N(v) \cap (R - S_R) \ne \emptyset$, $v$ is connected $R - S_R$. Then $CJC_n - S$ is connected, a contraction). Thus, $N(v) = S$ and $CJC_n - S - \{v\}$ is still connected.

**Lemma 4.** For any vertex $u$ of $V(EQ_{n,2})(n \ge 6)$, the connectivity of $EQ_{n,2} - N[u]$ is $\kappa(EQ_{n,2} - N[u]) = n - 1$.

Proof. $EQ_{n,2}$ can be viewed as $L \oplus R$, where $L$ (respectively, $R$) is subgraph of $EQ_{n,2}$ with the prefix 0 (respectively, 1) of each vertex. And we have $L \cong R \cong EQ_{n-1,2}$.

Since $\delta(EQ_{n,2} - N[u]) = n - 1$, $\kappa(EQ_{n,2} - N[u]) \le n - 1$. Now, we show that $\kappa(EQ_{n,2} - N[u]) \ge n - 1$ in the following.

Let $S$ be the subset of $V(EQ_{n,2} - N[u])$ with $|S| = n - 2$. Denote $S_L = S \cap L$ and $S_R = S \cap R$. Without loss of generality, we assume that $u$ is in $L$.

Since $|S_R| + |N[u] \cap R| \le n - 2 + 1 < n$, by Remark 3(2), $R - N[u] - S_R$ is connected. Then we need only to show that any vertex $v \in V(L - N[u] - S_L)$ is connected to $R - N[u] - S_R$.

If $N(v) \cap (R - N[u] - S_R) \ne \emptyset$, we are done; otherwise, by the fact of

$$ |N(v)| = n + 1 > |N(v) \cap N(u)| + |S| = 2 + n - 2, $$

we have that $N(v) \cap (L - N[u] - S_L) \ne \emptyset$. Without loss of generality, we set $v_0 \in V(N(v) \cap (L - N[u] - S_L))$. Then there must exist one vertex

$$ v_1 \in V(N(v, v_0) \cap (L - N[u] - S_L)) $$

such that $N(v_1) \cap (R - N[u] - S_R) \ne \emptyset$ (otherwise, $|N(v, v_0) \cap L| - |S_L| \le |S_R|$, which means that $|N(v, v_0) \cap L| < |S|$, i.e., $2n - 4 < n - 2$, a contradiction). Therefore, $v$ is connected to $R - N[u] - S_R$ and $EQ_{n,2} - N[u] - S$ is still connected.

**Lemma 5.** Let $\{u, v\}$ be a pair of adjacent vertices of $V(CJC_n)(n \ge 6)$. Then $\kappa(CJC_n - N[u, v]) \ge n - 2$.
**Proof.** Let $S$ be a subset of $V(CJC_n - N[u, v])$ with $|S| = n-3$. Let $S_L = S \cap L$ and $S_R = S \cap R$.

**Case 1** both of $u$ and $v$ are in $L$ (respectively, $R$).

Since $|N(w) \cap N[u, v]| \le 2$ for any vertex $w \in R$, by Remark 3(2), we have that $R - N[u, v] - S_R$ is still connected.

If $N(x) \cap (R - N[u, v] - S_R) \neq \emptyset$ for any vertex $x \in L - N[u, v] - S_L$, we are done; otherwise, there exists a neighbor of $x$ in $L - N[u, v] - S_L$, say $x_0$. Then there must exist one vertex

$$x_1 \in V(N(x, x_0) \cap (L - N[u] - S_L))$$

such that $N(x_1) \cap (R - N[u] - S_R) \neq \emptyset$ (otherwise, $|N(x, x_0) \cap L| - |S_L| \le |S_R|$, which means that $|N(x, x_0) \cap L| < |S|$, i.e., $2n - 4 < n - 3$, a contradiction). Thus, $x$ is connected to $R$ through the $C$-link or $H$-link of $x_1$. Therefore, $CJC_n - N[u, v] - S$ is still connected.

**Case 2** $u$ is in $L$ and $v$ is in $R$ (respectively, $u$ is in $R$ and $v$ is in $L$).

**Subcase 2.1** $|S_L| \le n - 4$ and $|S_R| \le n - 4$.

Taking into account that

$$|S_L| + |N(v) \cap L| \le n - 4 + 1 = n - 3$$

and

$$|S_R| + |N(u) \cap R| \le n - 4 + 1 = n - 3,$$

by Lemma 4, both of $L - N[u, v] - S_L$ and $R - N[u, v] - S_R$ are still connected. Since $|L - N[u, v] - S_L| > |N[u, v] \cap R| + |S_R|$ (i.e., $2^{n-1} - (n+2) > (n+2) + (n-3)$ for $n \ge 6$), $L - N[u, v] - S_L$ is connected to $R - N[u, v] - S_R$, which means that $CJC_n - N[u, v] - S$ is connected.

**Subcase 2.2** $|S_L| = n - 3$ and $|S_R| = 0$ (respectively, $|S_R| = n - 3$ and $|S_L| = 0$).

By Lemma 4, $R - N[u, v] - S_R$ is connected. Then we need only to show that any vertex $w \in V(L - N[u, v] - S_L)$ is connected to $R - N[u, v] - S_R$.

If $N(w) \cap (R - N[u, v] - S_R) \neq \emptyset$, we are done; otherwise, by the fact of

$$|N(w)| = n + 2 > |N(w) \cap N(u, v)| + |S| = 4 + n - 3,$$

we have that

$$N(w) \cap (L - N[u, v] - S_L) \neq \emptyset.$$

Without loss of generality, we set $w_0 \in V(N(w) \cap (L - N[u, v] - S_L))$. Then there must exist one vertex $w_1 \in V(N(w, w_0) \cap (L - N[u] - S_L))$ with $N(w_1) \cap (R - N[u, v] - S_R) \neq \emptyset$ (otherwise, $|N(w, w_0) \cap L| - |S_L| \le |S_R|$, which means that $|N(w, w_0) \cap L| < |S|$, i.e., $2n - 4 < n - 3$, a contradiction). Therefore, $w$ is connected to $R - N[u, v] - S_R$ and $CJC_n - N[u, v] - S$ is still connected.

**Theorem 1.** Let $S$ be a subset of at most $3n - 3$ vertices of $V(CJC_n)(n \ge 6)$. Under the conditional fault model, that is, $N(u) \notin S$ for any vertex $u \in V(CJC_n)$, $CJC_n - S$ satisfies one of the following conditions:

(1) $CJC_n - S$ is connected; or

(2) $CJC_n - S$ has exactly two connected components, one of which is $K_2$ and the other one has $2^n - |S| - 2$ vertices.
**Proof.** Let $S_L = S \cap L$ and $S_R = S \cap R$ with the restriction that $|S| \le 3n-3$.

**Case 1** $N(u, v) \not\subseteq S$ for any pair of adjacent vertices $\{u, v\}$ of $CJC_n$.

**Subcase 1.1** Either $|S_L| \ge 2n-2$ or $|S_R| \ge 2n-2$.

Without loss of generality, we assume that $|S_R| \ge 2n-2$. Then $|S_L| \le 3n-3-(2n-2) \le n-1 < \kappa(EQ_{n-1,2})$, by Remark 3(1), we have that $L-S_L$ is still connected. Now we show that there exists a path connecting $u$ to $L-S_L$ for any vertex $u \in R-S_R$. Let $u_L$ and $u_c$ be the neighbors of $u$, which are in $L$.

If at least one of $u_L$ and $u_c$ is not in $S_L$, we are done; otherwise, since $N(u) \not\subseteq S$, there exists one neighbor $v \in (R-S_R)$ of $u$. If $N(v) \cap (R-S_R) \ne \emptyset$, we are done; otherwise, since $N(u,v) \not\subseteq S$, there must exist one vertex $w \in N(u,v) \cap (R-S_R)$ such that $N(w) \cap (L-S_L) \ne \emptyset$ (otherwise, since $|N(u,v) \cap R| \ge 2n-4$ and all these $2n-4$ vertices have at least $2n-4$ neighbors in $L$, $|S_L| \ge 2n-4$. Then $|S| \ge 2n-4+2n-2 > 3n-2$, a contradiction). Therefore, $u$ can connect to $L-S_L$ which means that $CJC_n-S$ is connected.

**Subcase 1.2** $|S_L| \le 2n-3$ and $|S_R| \le 2n-3$.

If one of two subgraphs $L-S_L$ and $R-S_R$ is connected, the discussion is similar to that of Subcase 1.1. Now we assume that both of $L-S_L$ and $R-S_R$ are disconnected.

<figure><img src="image_4.png" /><figcaption>Figure 2. Illustration in Theorem 1 for the example of subcase 1.2.1</figcaption></figure>

**Subcase 1.2.1** $|S_L| \le 2n-5$ and $|S_R| \le 2n-5$.

In this case, by Remark 1, there must exist one vertex $u \in L-S_L$ (respectively, $v \in R-S_R$) such that $N(u) \cap L \subset S_L$ (respectively, $N(v) \cap R \subset S_R$), and both of $L-S_L-N[u]$ and $R-S_R-N[v]$ are still connected.

We now show that the four parts $\{u\}$, $\{v\}$, $L-S_L-N[u]$ and $R-S_R-N[v]$ constitute exactly one connected component.

If $u$ is connected to $v$, by the assumption that $N(u,v) \not\subseteq S$, either $N(u) \cap (R-S_R - \{v\}) \ne \emptyset$ or $N(v) \cap (L-S_L - \{u\}) \ne \emptyset$ holds (Figure 2(a)). Now we assume that $u$ and $v$ are not adjacent, by the assumption that $N(u) \not\subseteq S$ and $N(v) \not\subseteq S$, $N(u) \cap (R-S_R - \{v\}) \ne \emptyset$ and $N(v) \cap (L-S_L - \{u\})$ holds (Figure 2(b)).

Furthermore, $|L-S_L - \{u\}| > |S_R \cup \{v\}|$ (i.e., $|L| - |S_L| - 1 > |S_R| + 1$) and there exists a perfect matching between $L$ and $R$, $L-S_L - \{u\}$ is connected to $R-S_R - \{v\}$.

By the discussion above, we obtain that $CJC_n-S$ is connected.
**Subcase 1.2.2** $2n - 4 \le |S_L| \le 2n - 3$ or $2n - 4 \le |S_R| \le 2n - 3$.

Without loss of generality, we assume that $2n - 4 \le |S_R| \le 2n - 3$, then $n \le |S_L| \le n + 1$. Since $L$ (respectively, $R$) has $Q_{n-1}$ as its subgraph, by Remark 1, there are exactly two components of $L - S_L$, one of which is trivial, say $\{u\}$. By Remark 3(3)(4), we obtain that in $R - S_R$, there are exactly two components, one of which is trivial or one isolated edge.

If the smaller one of the two components of $R - S_R$ is trivial, say $u$, then the discussion is the same as subcase 1.2.1. If the smaller one of the two components of $R - S_R$ is an isolated edge, say $\{v_0, v_1\}$, by the assumption that $2n - 4 \le |S_R| \le 2n - 3$, $|N(v_0, v_1)| = 2n - 4$. If $u$ is connected to the edge $(v_0, v_1)$, $|N(u, v_0, v_1)| = 3n - 1 > 3n - 3$, and $\{u, v_0, v_1\}$ is connected to $L - S_L$ or $R - S_R$. If $u$ is not connected to the edge $(v_0, v_1)$, by the assumption that $N(u) \not\subseteq S$, $u$ is connected to $R - S_R$. Since there are 4 neighbors of $\{v_0, v_1\}$ in $L$ and $n \le |S_L| \le n + 1$, $\{v_0, v_1\}$ is connected to $L - S_L$. Since $|L - S_L - \{u\}| > |S_R \cup \{v_0, v_1\}|$ (i.e., $|L| - |S_L| - 1 > |S_R| + 2$) and there exists a perfect matching between $L$ and $R$, $L - S_L - \{u\}$ is connected to $R - S_R - \{v_0, v_1\}$. Therefore we obtain that $CJC_n - S$ is connected.

**Case 2** There exists a pair of adjacent vertices $\{u, v\}$ of $G$ such that $N(u, v) \subset S$. Since $|S \cap N(u, v)| \ge |N(u, v)| \ge 2n$, we have

$$|S - N(u, v)| = |S| - |S \cap N(u, v)| \le 3n - 3 - 2n = n - 3.$$

By Lemma 5, $CJC_n - S - N[u, v]$ is connected. So the graph $CJC_n - S$ has exactly two components, one of which is $K_2[u, v]$, the other is $CJC_n - S - \{u, v\}$.

# 4 The Conditional Diagnosability of $CJC_n$

The comparison diagnosis strategy can be modeled as a multi-graph $M = (V, C)$, where $V$ is the same node set defined as in $G$, $C$ is the labelled edge set. A labelled edge $(u, v)_w$ is said to belong to $C$ if $(u, v)$ is an edge labeled by $w$, which implies that the processors $u$ and $v$ are compared by processor $w$. Since different comparators can compare the same pair of processors, $M$ is a multi-graph. Denote the comparison result as $\sigma((u, v)_w)$ such that $\sigma((u, v)_w) = 0$ if the outputs of $u$ and $v$ agree, and $\sigma((u, v)_w) = 1$ if the outputs disagree. If the comparator $w$ is fault-free and $\sigma((u, v)_w) = 0$, the processors $u$ and $v$ are fault-free; while $\sigma((u, v)_w) = 1$, at least one of the three processors $u$, $v$ and $w$ is faulty. The collection of the comparison results defined as a function $\sigma: C \to \{0, 1\}$, is called the syndrome of the diagnosis. A subset $F \subsetneq V$ is said to be compatible with a syndrome $\sigma$ if $\sigma$ can arise from the circumstance that all vertices in $F$ are faulty and all vertices in $V \setminus F$ are fault-free. A faulty comparator can lead to unreliable results, so a set of faulty vertices may produce different syndromes.

Let $\sigma_F = \{\sigma | \sigma$ is compatible with $F\}$. Two distinct subsets $F_1$ and $F_2$ of $V(G)$ are said to be indistinguishable if and only if $\sigma_{F_1} \cap \sigma_{F_2} \neq \emptyset$; otherwise, both of $F_1$ and $F_2$ are said to be distinguishable. There are several different ways to verify whether a system is t-diagnosable under the comparison approach. The
following lemma obtained by Sengupta and Dahbura [12] gives necessary and sufficient conditions to ensure distinguishability.

**Lemma 6.** [12] Let $G$ be a graph. For any two distinct subsets $F_1, F_2$ of $V(G)$. $(F_1, F_2)$ is a distinguishable pair if and only if at least one of the following conditions is satisfied.

(1) There are two distinct vertices $u, w \in V(G) - (F_1 \cup F_2)$ and there is a vertex $v \in F_1 \Delta F_2$ such that $(u, v)_w \in C$;

(2) There are two distinct vertices $u$ and $v \in F_1 \setminus F_2$ and there is a vertex $w \in V(G) - (F_1 \cup F_2)$ such that $(u, v)_w \in C$; or

(3) There are two distinct vertices $u, v \in F_2 \setminus F_1$ and there is a vertex $w \in V(G) - (F_1 \cup F_2)$ such that $(u, v)_w \in C$.

Lin et al. [8] introduced the so-called conditional diagnosability of a system under the situation that no set of faulty vertices can contain all neighbors of any vertex in the system. A faulty set $F \subset V(G)$ is called a conditional faulty set if $N_G(v) \not\subseteq F$ for every vertex $v \in V(G)$. A system $G(V, E)$ is said to be conditionally $t$-diagnosable if $F_1$ and $F_2$ are distinguishable for each pair of distinct conditional faulty set $F_1$ and $F_2$ with $|F_1| \le t, |F_2| \le t$. The maximum value of $t$ such that $G$ is conditionally $t$-diagnosable is called the conditional diagnosability of $G$, denoted by $t_C(G)$. It is trivial that $t_C(G) \ge t(G)$.

**Lemma 7.** Let $F_1$ and $F_2$ be any two distinct conditional faulty subset of $CJC_n$ with $|F_1| \le 3n-2$ and $|F_2| \le 3n-2$, and $H$ be the maximum component of $CJC_n - F_1 \cap F_2$. Then for any vertex $u \in F_1 \Delta F_2$, we have $u \in H$.

**Proof.** Without loss of generality, let $u \in F_1 - F_2$.

Since $F_2$ is the conditional faulty subset, there is a vertex $v \in CJC_n - F_2 - \{u\}$ such that $(u, v) \in E(CJC_n)$. Assume that $u \notin H$. Then we have $v \notin H$. In other words, $(u, v)$ is the small component of $CJC_n - F_1 \cap F_2$. Obviously, $|F_1 \cap F_2| \le 3n-3$. Since $F_1$ and $F_2$ are two distinct conditional faulty subset of $CJC_n$. By Theorem 1, $(u, v)$ is a component $K_2$ of $CJC_n - F_1 \cap F_2$, and $N(u, v) \subset F_1 \cap F_2$. In addiction, $u \in F_1 - F_2$, so that all the neighbors of $v$ are in $F_1$. However, since $F_1$ is the conditional faulty subset, so we have $u \in H$.

**Lemma 8.** [8] Let $G$ be a graph with $\delta(G) \ge 2$, and let $F_1$ and $F_2$ be any two distinct conditional faulty subsets of $G$. If either $F_1 \subset F_2$ or $F_2 \subset F_1$, $(F_1, F_2)$ is a distinguishable conditional pair under the comparison diagnosis model.

**Theorem 2.** The conditional diagnosability of the Complete Josephus Cube $CJC_n$ under the comparison diagnosis model is $t_c(CJC_n) = 3n-2$ ($n \ge 8$).

**Proof.** First, we prove that $t_c(CJC_n) \le 3n-2$.

There exist three vertices $u, v, w \in V(CJC_n)$, such that $(u, w, v)$ is in a cycle of length 3. We set $A = N[u, v, w]$, $F_1 = A - \{w, v\}$, and $F_2 = A - \{u, w\}$. We get $|F_1| = |F_2| = 3(n-1) + 2 = 3n-1$, and $|F_1 - F_2| = |F_2 - F_1| = 1$. It is easy to check that $F_1$ and $F_2$ are two conditional faulty sets, and $F_1$ and $F_2$ are indistinguishable. Hence, we have the result $t_c(CJC_n) \le 3n-2$.
Second, we prove that $t_c(CJC_n) \ge 3n-2$. Suppose that $F_1$ and $F_2$ are two distinct conditional faulty subsets of $CJC_n$ with $|F_1| \le 3n-2$ and $|F_2| \le 3n-2$. Then it is suffice to prove that $(F_1, F_2)$ is distinguished under the comparison diagnosis model.

By Lemma 8, if one of $F_2 \subset F_1$ and $F_1 \subset F_2$ holds, then $(F_1, F_2)$ is distinguishable.

Now we assume $F_2 \not\subset F_1$ and $F_1 \not\subset F_2$, which implies that $|F_1 - F_2| \ge 1$ and $|F_2 - F_1| \ge 1$. We have $|F_1 \cap F_2| \le 3n-3$.

Let $H$ be the maximum component of $CJC_n - F_1 \cap F_2$. By Lemma 7, any vertex in $F_1 \Delta F_2$ is in $H$.

We claim that $H$ has a vertex, say $u$, outside of $F_1 \cup F_2$ that has no neighbor $F_1 \cap F_2$. Since every vertex of $CJC_n$ has degree $n+2$, those vertices in $F_1 \cap F_2$ have at most $(n+2)|F_1 \cap F_2|$ neighbors in $H$ in total. There are at most $2(3n-2) - |F_1 \cap F_2|$ vertices in $F_1 \cup F_2$ and at most two vertices of $CJC_n - F_1 \cap F_2$ may not belong to $H$ by Theorem 1. Since $|F_1 \cap F_2| \le 3n-3$, we have

$$ 
\begin{aligned}
& 2^n - (n+2)|F_1 \cap F_2| - (2(3n-2) - |F_1 \cap F_2|) - 2 \\
& \ge 2^n - (n+1)|F_1 \cap F_2| - 2(3n-2) - 2 \\
& \ge 2^n - n(3n-3) - 2(3n-2) - 2 \\
& = 2^n - 3n^2 - 3n + 2 \\
& > 2 (n \ge 8).
\end{aligned}
$$

Thus, there must be some vertex of $H$ outside $F_1 \cup F_2$, which has no neighbors in $S$. Let $u$ be such a vertex.

If $u$ has no neighbor in $F_1 \cup F_2$, then we can find a path of length at least two within $H$ to a vertex $v$ in $F_1 \cup F_2$. We may assume that $v$ is the first vertex of $F_1 \Delta F_2$ on this path, and let $q$ and $w$ be the two vertices on this path immediately before $v$ (we may have $u = q$), so $q$ and $w$ are not in $F_1 \cup F_2$. The existence of the edges $(q, w)$ and $(w, v)$ shows that $(F_1, F_2)$ is a distinguishable conditional pair of $CJC_n$ by Lemma 6. Now we assume that $u$ has a neighbor in $F_1 \Delta F_2$. Since the degree of $u$ is at least 3, and $u$ has no neighbor in $S$, there are three possibilities:

(1) $u$ has two neighbors in $F_1 - F_2$; or

(2) $u$ has two neighbors in $F_2 - F_1$; or

(3) $u$ has at least one neighbor outside $F_2 \cup F_1$.

In each subcase above, Lemma 6 implies that $(F_1, F_2)$ is a distinguishable conditional pair of $CJC_n$ under the comparison diagnosis model.

## References

1. K.Y. Chwa, S.L. Hakimi, On fault identification in diagnosable system, IEEE Transactions on Computers C-30(6), 414-422(1981)

2. N.-W. Chang, S.-Y.n Hsieh, Conditional diagnosability of augmented cubes under the PMC model, IEEE Transations on Dependable and Secure Computing, 9(1), 46-60 (2012)
3. A.H. Esfahanian, Generalized measures of fault tolerance with application to $n$-cube networks, IEEE Transactions on Computers 38, 1586-1591 (1989)

4. G.-H. Hsu, C.-F. Chiang, L.-M. Shih, L.-H. Hsu, J.J.M. Tan, Conditional diagnosability of hypercubes under the comparison diagnosis model, Journal of Systems Architecture 55(2), 140-146 (2009)

5. P.K.K. Loh, W.J. Hsu, The Josephus Cubes: a novel interconnection network, Parallel Computing 26, 427-453 (2000)

6. P.K.K. Loh, W.J. Hsu, Fault-tolerant routing for complete Josephus Cubes, Parallel Computing 30, 1151-1167 (2004)

7. P.-L. Lai, J.J.M. Tan, C.-P. Chang, L.-H. Hsu, Conditional diagnosability measure for large multiprocessors systems, IEEE Transactions on Computers 54, 165-175 (2005)

8. C.-K. Lin, J.J. M. Tan, L.-H. Hsu, E. Cheng, Lipták, Conditional diagnosability of cayley graphs generalized by transposition tree under the comparison diagnosis model. Journal of Interconnection networks 9, 83-97 (2008)

9. M. Malek, A comparison connection assignment for diagnosis of multiprocessor systems, Proc. 7th int. Symp. Comput. Architecture, pp.31-35 (1980)

10. P. Manuel, Minimum average congestion of enhanced and augmented hypercubes into complete binary trees, Discrete Applied Mathematics 159, 360-366 (2011)

11. F.P. Preparata, G. Metze, R.T. Chien, On the connection assignment problem of diagnosable systems, IEEE Transactions on Computers 16, 848-854 (1967)

12. A. Sengupta, A. Dahbura, On self-diagnosable multiprocessor systems: diagnosis by the comparison approach, IEEE Transaction on Computers 41, 1386-1396 (1992)

13. N.-F. Tzeng, S.Z. Wei, Enhanced hypercubes, IEEE Transactions on Computers 40(3), 284-294 (1991)

14. D. Wang, Diagnosability of hypercubes and enhanced hypercubes under the comparison diagnosis model, IEEE Transaction on Computers 48(12), 1369-1374 (1999)

15. J.-M. Xu, Q. Zhu, X. Hou, T. Zhou, On restricted connectivity and extra connectivity of hypercubes and folded hypercubes, J.shanghai Jiaotong Univ. (Sci.) E-10(2), 208-212 (2005)

16. X. Yang, D.J. Evans, G.M. Megson, H.J. Lai, On the maximal connected component of a hypercube with faulty vertices III, International Journal of Computer Mathematics 83, 27-37 (2006)

17. Q. Zhu, Studies of fault tolerance and diagnosability of interconnection networks, Ph. D. Thesis, University of Science and Technology of China, 2005.

18. S. Zhou, The conditional diagnosability of crossed cubes under the comparison model, International Journal of Computer and Mathematics, 87(15), 3387-3396 (2010)

19. Q. Zhu, S.-Y. Liu, M. Xu, On conditional diagnosability of the folded hypercubes, Information Sciences 178, 1069-1077 (2008)

20. Q. Zhu, J.-M. Xu, M. X, On reliability of the folded hypercubes, Information Sciences, 177, 1782-1788 (2007)