Reliability Analysis of Crossed Cube Networks on Degree

Litao Guo

School of Applied Mathematics, Xiamen University of Technology, Xiamen, China.

DOI: 10.4236/jcc.2018.61014                

Abstract

Crossed cubes network is a kind of interconnection structure as a basis for distributed memory parallel computer architecture. Reliability takes an important role in fault tolerant computing on multiprocessor systems. Connectivity is a vital metric to explore fault tolerance and reliability of network structure based on a graph model. Let be a connected graph. The k-conditional edge connectivity is the cardinality of the minimum edge cuts , if any, whose deletion disconnects and each component of has property of minimum degree . The k-conditional connectivity can be defined similarly. In this paper, we determine the k- conditional (edge) connectivity of crossed cubes for small k. And we also prove other properties of .

Keywords

Interconnection Structure, Fault Tolerance, Reliability, Conditional Connectivity

1. Introduction

With the development of VLSI technology and software technology, multiprocessor systems with hundreds of thousands of processors have become available. With the continuous increase in the size of multiprocessor systems, the complexity of a system can adversely affect its fault tolerance and reliability. To the design and maintenance purpose of multiprocessor systems, appropriate measures of reliability should be found.

A network is often modeled by a graph $G=(V,E)$ with the vertices representing nodes such as processors or stations, and the edges representing links between the nodes. One fundamental consideration in the design of networks is reliability [1] [2]. An edge cut of a connected graph $G$ is a set of edges whose removal disconnects $G$ . The edge connectivity $\lambda (G)$ or connectivity $\kappa (G)$ of $G$ is the minimum cardinality of an edge cut or vertex cut $S$ of $G$ . The edge connectivity $\lambda (G)$ or connectivity $\kappa (G)$ is an important feature determining reliability and fault-tolerance of the network. In the definitions of $\lambda (G)$ or $\kappa (G)$ , no restrictions are imposed on the components of $G-S$ . To compensate for this short coming, it would seem natural to generalize the notion of the classical connectivity by imposing some conditions or restrictions on the components of $G-S$ . Following this idea, conditional connectivity were proposed in [3] by Harary.

Let $G$ be a connected graph and $P$ be graph-theoretic property. The conditional edge connectivity $\lambda (G,P)$ or conditional connectivity $\kappa (G,P)$ is the minimum cardinality of a set of edges or vertices, if it exists, whose deletion disconnects $G$ and each remaining component has property $P$ . In particular, we focus on that each component has the property of minimum degree $\delta \ge k$ . The k-conditional edge connectivity ${\lambda }^k(G)$ is the cardinality of the minimum edge cuts $F$ , if any, whose deletion disconnects $G$ and each component of $G-F$ has property of minimum degree $\delta \ge k$ . The k-conditional connectivity ${\kappa }^k(G)$ can be obtained similarly. In recent years, numerous results about many kind of connectivities on networks have been reported [4]-[20].

Let $G=(V,E)$ be a connected graph, $N_G(v)$ the neighbors of avertex $v$ in $G$ (simply $N(v)$ ), $E(v)$ the edges incident to $v$ . Moreover, for $S\subset V$ , $G[S]$ is the subgraph induced by $S$ , $N_G(S)={\cup }_{v\in S}N(v)-S$ , $E_G(S)={\cup }_{v\in S}E(v)-E(G[S])$ , $N_G[S]=N_G(S)\cup S$ and $G-S$ denotes the subgraph of $G$ induced by the vertex set of $V\setminus S$ . If $u,v\in V$ , $d(u,v)$ denotes the length of a shortest $(u,v)$ -path. For $X,Y\subset V$ , denote by $[X,Y]$ the set of edges of $G$ with one end in $X$ and the other in $Y$ . For graph-theo- retical terminology and notation not defined here we follow [21]. All graphs considered in this paper are simple, finite and undirected.

Two binary strings $x=x_1{x}_0$ and $y=y_1{y}_0$ are pair-related, denoted $x~y$ , if and only if $(x,y)\in \{(00,00),(10,10),(01,11),(11,01)\}$ ; if $x$ and $y$ are not pair-related, we write $x\nsim y$ .

The crossed cube $C{Q}_n$ with $2^n$ vertices was introduced by Efe [22]. It can be defined inductively as follows: $C{Q}_1$ is $K_2$ , the complete graph with labels 0 and 1. For $n>1$ , $C{Q}_n$ contains $C{Q}_{n-1}^0$ and $C{Q}_{n-1}^1$ joined according to the following rule: the vertex $u=0u_{n-2}\cdots u_0$ from and the vertex $v=1v_{n-2}\cdots v_0$ from $C{Q}_{n-1}^1$ are adjacent if and only if

1) $u_{n-2}=v_{n-2}$ if $n$ is even, and

2) for $0\le i<\lfloor (n-1)/2\rfloor ,u_{2i+1}{u}_{2i}~v_{2i+1}{v}_{2i}$ .

From the definition, we can see that each vertex of $C{Q}_n$ with a leading 0 bit has exactly one neighbor with a leading 1 and vice versa. It is an n-regular graph. In fact, some pairs of parallel edges are changed to some pairs of cross edges. Furthermore, $C{Q}_n$ can be obtained by adding a perfect matching $M$ between $C{Q}_{n-1}^0$ and $C{Q}_{n-1}^1$ . Hence $C{Q}_n$ can be viewed as $G(C{Q}_{n-1}^0,C{Q}_{n-1}^1,M)$ or $C{Q}_{n-1}^0\odot C{Q}_{n-1}^1$ briefly. For any vertex $u\in V(C{Q}_n),e_M(u)$ is the edge incident to $u$ in $M$ .

The crossed cube is an attractive alternative to hypercubes $Q_n$ . The diameter of $C{Q}_n$ is approximately half that of $Q_n$ . For more references, we can see [23]-[29] (Figure 1).

In this paper, we obtain that: ${\lambda }^2(C{Q}_n)=4n-8(n\ge 4)$ , and we also prove other properties of $C{Q}_n$ .

2. Conditional Connectivity of Crossed Cubes

The crossed cube $C{Q}_n$ has an important property as follows.

Lemma 2.1. Any two vertices of $C{Q}_n$ have at most two common neighbors for $n\ge 2$ if they have.

Proof: By induction. If $n=2$ , then the result holds. We assume that it is true for $n<k$ . Suppose $n=k$ and any $u,v\in V(C{Q}_n)$ such that $u,v$ have at most two common neighbors.

If $u,v\in V(C{Q}_{n-1})$ , then the two common neighbors are in $V(C{Q}_{n-1})$ according to inductive hypothesis. And there is not a relation between the common neighbors of $u,v$ and the perfect matching $M$ added to $C{Q}_n$ . Hence $u,v$ have at most two common neighbors in $C{Q}_n$ .

By symmetry, we assume that $u\in V(C{Q}_{n-1}^0),v\in V(C{Q}_{n-1}^1)$ . The common neighbors must be obtained by adding the perfect matching $M$ . Note that every vertex of $C{Q}_{n-1}^0$ has only one neighbor in $C{Q}_{n-1}^1$ and vice versa. Then we obtain the result.

Corollary 2.2. For any two vertices $x,y\in V(C{Q}_n)(n\ge 2)$ ,

1) if $d(x,y)=2$ , then they have at most two common neighbors;

2) if $d(x,y)\ne 2$ , then they do not have common neighbors.

Figure 1. Crossed cube for $n=3,4$ .

Corollary 2.3. The girth of $C{Q}_n$ is $4(n\ge 2)$ .

According to the definition of $C{Q}_n$ , and similar to Lemma 2.1, we have

Lemma 2.4. Let $x$ and $y$ be any two vertices of $V(C{Q}_n)(n\ge 2)$ such that have only two common neighbors.

1) If $x\in V(C{Q}_{n-1}^0),y\in V(C{Q}_{n-1}^1)$ , then the one common neighbor is in $C{Q}_{n-1}^0$ , and the other one is in $C{Q}_{n-1}^1.$

2) If $x,y\in V(C{Q}_{n-1}^0)$ or $V(C{Q}_{n-1}^1)$ , then the two common neighbors are in $C{Q}_{n-1}^0$ or $C{Q}_{n-1}^1$ .

Lemma 2.5. Let $A$ be an induced subgraph of $C{Q}_n$ and $\delta (A)\ge 2$ .

1) $|V(A)|\ge 4$ .

2) If $V(A)\cap V(C{Q}_{n-1}^i)\ne \varnothing$ , then $|V(A)\cap V(C{Q}_{n-1}^i)|\ge 2(i=0,1)$ .

3) If $|V(A)|=4$ , then $A$ is a 4-cycle $C_4$ and $|V(A)\cap V(C{Q}_{n-1}^i)|=2(i=0,1)$ .

Proof:

Because $\delta (A)\ge 2$ and The girth of $C{Q}_n$ is 4, $|V(A)|\ge 4$ . If $|V(A)|=4$ , then $A$ is a 4-cycle $C_4$ .

Assume that $|V(A)\cap V(C{Q}_{n-1}^0)|=1$ . Let $\left\{x\right\}=V(A)\cap V(C{Q}_{n-1}^0)$ . Since $d(x)\ge 2$ , $x$ has at least two neighbors in $V(C{Q}_{n-1}^1)$ , which is a contracted to the definition of $C{Q}_n$ . Hence $|V(A)\cap V(C{Q}_{n-1}^i)|=2(i=0,1)$ . If $|V(A)|=4$ , then $|V(A)\cap V(C{Q}_{n-1}^i)|=2(i=0,1)$ .

Theorem 2.6.

${\lambda }^2(C{Q}_n)=4n-8(n\ge 4)$ .

Proof:

Take a 4-cycle $C_4$ in $C{Q}_n$ . Clearly, $|E(C_4)|=4n-8$ and $C{Q}_n-E(C_4)$ is not connected and minimum degree of each component is at least two. Then ${\lambda }^2(C{Q}_n)\le 4n-8$ .

We will show ${\lambda }^2(C{Q}_n)\ge 4n-8$ by induction. It is easy to check that holds for $n=4$ . So we suppose $n\ge 5$ . Assume that it is true for $n<k$ . Let $n=k$ .

Let $F\subseteq E(C{Q}_n)$ with $\left|F\right|\le 4n-9$ . And $C{Q}_n-F$ is not connected and minimum degree of each component is at least two. We have $|F\cap E(C{Q}_{n-1}^0)|\le 2n-5$ or $|F\cap E(C{Q}_{n-1}^1)|\le 2n-5$ . Without loss of generality, we set $|F\cap E(C{Q}_{n-1}^0)|\le 2n-5$ . And $C{Q}_{n-1}^0-F$ is connected from the inductive hypothesis. We will show that every vertex of $C{Q}_{n-1}^1-F$ is connected to $C{Q}_{n-1}^0-F$ .

If there is a vertex $u$ of $C{Q}_{n-1}^1-F$ with $d_{C{Q}_{n-1}^1-F}(u)=1$ , then by the hypothesis $u$ is connected to $C{Q}_{n-1}^0-F$ , a contradiction. Hence for any vertex $u$ of $C{Q}_{n-1}^1-F$ , we have $d_{C{Q}_{n-1}^1-F}(u)\ge 2$ . Let $H$ be an any component of $C{Q}_{n-1}^1-F$ . Since $\delta (G)\ge 2$ , we have $|V(H)|\ge 4$ and $u_i\in V(H)(i=1,2,3,4)$ by Lemma 2.6. Suppose $C=\{N_{C{Q}_{n-1}^1}(u_i):i=1,2,3,4\}$ and $\left|C\right|\ge 4n-12$ . Let $x$ be a some vertex of $C$ . Because of $\left|F\right|\le 4n-9$ , at least one vertex of $\{u_1,u_2,u_3,u_4,x\}$ has a neighbor in $C{Q}_{n-1}^0-F$ . Then $H$ is connected to $C{Q}_{n-1}^0-F$ . Moreover, $C{Q}_n-F$ is connected, a contradiction.

3. Conclusion

The conditional connectivity is a generalization of classical connectivity of graphs. We determined the r-conditional degree connectivity of $C{Q}_n$ for the small r. In the future, we will study other properties of crossed cubes.

Acknowledgements

The authors would like to thank the referees for kind help and valuable suggestions.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Cheng, E., Lesniak, L., Lipman, M. and Liptak, L. (2009) Conditional Matching Preclusion Sets. Information Sciences, 179, 1092-1101. https://doi.org/10.1016/j.ins.2008.10.029
[2]	Lin, M., Chang, M. and Chen, D. (1999) Efficient Algorithms for Reliability Analysis of Distributed Computing Systems. Inform. Sci., 117, 89-106. https://doi.org/10.1016/S0020-0255(99)00003-1
[3]	Harary (1983) Conditional Connectivity. Networks, 13, 346 -357. https://doi.org/10.1002/net.3230130303
[4]	Fabrega, J. and Fiol, M. (1996) On the Extra Connectivity of Graphs. Discr. Math., 155, 49-57. https://doi.org/10.1016/0012-365X(94)00369-T
[5]	Guo, L. and Guo, X. (2009) Connectivity of the Mycielskian of a Digraph. Applied MathematicsLetters, 22, 1622-1625. https://doi.org/10.1016/j.aml.2009.05.007
[6]	Guo, L., Qin, C. and Guo, X. (2010) Super Connectivity of Kronecker Products of Graphs. Information Processing Letters, 110, 659-661. https://doi.org/10.1016/j.ipl.2010.05.013
[7]	Guo, L., Liu, R. and Guo, X. (2012) Super Connectivity and Super Edge Connectivity of the Mycielskian of a Graph. Graph and Combinatorics, 28, 143-147. https://doi.org/10.1007/s00373-011-1032-3
[8]	Guo, L. Fault Tolerance of Crossed Cubes. Submitted.
[9]	Guo, L. and Guo, X. (2014) Fault Tolerance of Hypercubes and Folded Hypercubes. J. Supercomput., 68, 1235-1240. https://doi.org/10.1007/s11227-013-1078-5
[10]	Lin, L., Xu, L. and Zhou, S. (2016) Relating the Extra Connectivity and the Conditional Diagnosability of Regular Graphs under the Comparison Model. Theoretical Comput. Sci., 618, 21-29. https://doi.org/10.1016/j.tcs.2015.12.031
[11]	Meng, J. and Ji, Y.H. (2002) On a Kind of Restricted Edgeconnectivty of Graphs. Discrete Applied Math., 117, 183-193. https://doi.org/10.1016/S0166-218X(00)00337-1
[12]	Meng, J. (2003) Optimally Super-Edge-Connected Transitive Graphs. Discrete Math., 260, 239-248. https://doi.org/10.1016/S0012-365X(02)00675-1
[13]	Sampathkumar, E. (1984) Connectivity of a Graph—A Generalization, J. Comb.Inf. Syst. Sci., 9, 71-78.
[14]	Wang, S., Wang, Z. and Wang, M. (2016) The 2-Extra Connectivity and 2-Extra Diagnosability of Bubble-Sort Star Graph Networks. The Computer Journal, 59, 1839-1856. https://doi.org/10.1093/comjnl/bxw037
[15]	Xu, J. (2001) Topological Structure and Analysis of Inter-connection. Kluwer Academic Publishers, Network.
[16]	Yang, W. and Li, H. (2014) On Reliability of the Folded Hyper-cubes in Terms of the Extra Edge-Connectivity. Inform. Sci., 272, 238-243. https://doi.org/10.1016/j.ins.2014.02.081
[17]	Zhao, S., Yang, W. and Zhang, S. (2016) Component Connectivity of Hypercubes. Theoretical Comput. Sci., 640, 115-118.
[18]	Zhang, M. and Zhou, J. (2015) On g-Extra Connectivity of Folded Hypercubes. Theoretical Comput. Sci., 593, 146-153. https://doi.org/10.1016/j.tcs.2015.06.008
[19]	Zhang, M., Zhang, L. and Feng, X. (2016) Reliability Measures in Relation to the h-Extra Edge-Connectivity of Folded Hypercubes. Theoretical Comput. Sci., 615, 71-77. https://doi.org/10.1016/j.tcs.2015.11.049
[20]	Zhang, Z., Xiong, W. and Yang, W. (2010) A Kind of Conditional Fault Tolerance of Alternating Group Graphs. Inform. Process. Lett., 110, 998-1002. https://doi.org/10.1016/j.ipl.2010.08.010
[21]	Bondy, J. and Murty, U. (1976) Graph Theory and Its Application. Academic Press, New York.
[22]	Efe, E. (1992) The Crossed Cube Architecture for Parallel Computing. IEEE Trans. Parallel Distrib. Systems, 3, 513-524. https://doi.org/10.1109/71.159036
[23]	Chang, C. and Wu, C. (2009) Conditional Fault Diameter of Crossed Cubes. J. Parallel Distrib. Comput., 69, 91-99. https://doi.org/10.1016/j.jpdc.2008.08.001
[24]	Efe, K., Blackwell, P.K., Slough, W. and Shiau, T. (1994) Topological Properties of the Crossed Cube Architecture. Parallel Computing, 20, 1763-1775. https://doi.org/10.1016/0167-8191(94)90130-9
[25]	Fan, J. (2002) Diagnosability of Crossed Cubes under the Comparison Diagnosis Model. IEEE Transactions on Parallel and Distributed Systems, 13, 1099-1104. https://doi.org/10.1016/0167-8191(94)90130-9
[26]	Fan, J., Lin, X. and Jia, X. (2005) Optimal Path Embedding in Crossed Cubes. IEEE Transactions on Parallel and Distributed Systems, 16, 1190-1200. https://doi.org/10.1109/TPDS.2005.151
[27]	Fan, J., Lin, X. and Jia, X. (2005) Node-Pancyclicity and Edge-Pancyclicityin Crossed Cubes. Information Processing Letters, 93, 133-138. https://doi.org/10.1016/j.ipl.2004.09.026
[28]	Kulasinghe, D. (1997) Connectivity of the Crossed Cube. Inform. Processing Let., 61, 221-226. https://doi.org/10.1016/S0020-0190(97)00012-4
[29]	Ma, M. and Xu, J. (2005) Edge-Pancyclicity of Crossed Cubes. J. China Univ. Sci. Tech., 35, 329-333.