Journal of Computer and Communications
Vol.06 No.01(2018), Article ID:81432,6 pages
10.4236/jcc.2018.61014
Reliability Analysis of Crossed Cube Networks on Degree
Litao Guo
School of Applied Mathematics, Xiamen University of Technology, Xiamen, China
Received: October 19, 2017; Accepted: December 26, 2017; Published: December 29, 2017
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 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 is a set of edges whose removal disconnects . The edge connectivity or connectivity of is the minimum cardinality of an edge cut or vertex cut of . The edge connectivity or connectivity is an important feature determining reliability and fault-tolerance of the network. In the definitions of or , no restrictions are imposed on the components of . 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 . Following this idea, conditional connectivity were proposed in [3] by Harary.
Let be a connected graph and be graph-theoretic property. The conditional edge connectivity or conditional connectivity is the minimum cardinality of a set of edges or vertices, if it exists, whose deletion disconnects and each remaining component has property . In particular, we focus on that each component has the property of minimum degree . 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 obtained similarly. In recent years, numerous results about many kind of connectivities on networks have been reported [4]-[20].
Let be a connected graph, the neighbors of avertex in (simply ), the edges incident to . Moreover, for , is the subgraph induced by , , , and denotes the subgraph of induced by the vertex set of . If , denotes the length of a shortest -path. For , denote by the set of edges of with one end in and the other in . 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 and are pair-related, denoted , if and only if ; if and are not pair-related, we write .
The crossed cube with vertices was introduced by Efe [22]. It can be defined inductively as follows: is , the complete graph with labels 0 and 1. For , contains and joined according to the following rule: the vertex from and the vertex from are adjacent if and only if
1) if is even, and
2) for .
From the definition, we can see that each vertex of 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, can be obtained by adding a perfect matching between and . Hence can be viewed as or briefly. For any vertex is the edge incident to in .
The crossed cube is an attractive alternative to hypercubes . The diameter of is approximately half that of . For more references, we can see [23]-[29] (Figure 1).
In this paper, we obtain that: , and we also prove other properties of .
2. Conditional Connectivity of Crossed Cubes
The crossed cube has an important property as follows.
Lemma 2.1. Any two vertices of have at most two common neighbors for if they have.
Proof: By induction. If , then the result holds. We assume that it is true for . Suppose and any such that have at most two common neighbors.
If , then the two common neighbors are in according to inductive hypothesis. And there is not a relation between the common neighbors of and the perfect matching added to . Hence have at most two common neighbors in .
By symmetry, we assume that . The common neighbors must be obtained by adding the perfect matching . Note that every vertex of has only one neighbor in and vice versa. Then we obtain the result.
Corollary 2.2. For any two vertices ,
1) if , then they have at most two common neighbors;
2) if , then they do not have common neighbors.
Figure 1. Crossed cube for .
Corollary 2.3. The girth of is .
According to the definition of , and similar to Lemma 2.1, we have
Lemma 2.4. Let and be any two vertices of such that have only two common neighbors.
1) If , then the one common neighbor is in , and the other one is in
2) If or , then the two common neighbors are in or .
Lemma 2.5. Let be an induced subgraph of and .
1) .
2) If , then .
3) If , then is a 4-cycle and .
Proof:
Because and The girth of is 4, . If , then is a 4-cycle .
Assume that . Let . Since , has at least two neighbors in , which is a contracted to the definition of . Hence . If , then .
Theorem 2.6.
.
Proof:
Take a 4-cycle in . Clearly, and is not connected and minimum degree of each component is at least two. Then .
We will show by induction. It is easy to check that holds for . So we suppose . Assume that it is true for . Let .
Let with . And is not connected and minimum degree of each component is at least two. We have or . Without loss of generality, we set . And is connected from the inductive hypothesis. We will show that every vertex of is connected to .
If there is a vertex of with , then by the hypothesis is connected to , a contradiction. Hence for any vertex of , we have . Let be an any component of . Since , we have and by Lemma 2.6. Suppose and . Let be a some vertex of . Because of , at least one vertex of has a neighbor in . Then is connected to . Moreover, 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 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.
Cite this paper
Guo, L.T. (2018) Reliability Analysis of Crossed Cube Networks on Degree. Journal of Computer and Communications, 6, 129-134. https://doi.org/10.4236/jcc.2018.61014
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.