Reliability Analysis of the Generalized Exchanged Hypercube
Abstract
Let be a non-complete graph, a subset is called a -component cut of , if is disconnected and has at least components. The cardinality of the minimum -component cut is the -component connectivity of and is denoted by . The -component connectivity is a natural extension of the classical connectivity. As an application, the -component connectivity can be used to evaluate the reliability and fault tolerance of an interconnection network structure based on a graph model. In a previous work, E. Cheng et al. obtained the -component connectivity of the generalized exchanged hypercube for and . In this paper, we continue the work and determine that for . Moreover, we show that every optimal -component cut of is trivial for and .
References
- 1. , Graph Theory and Its Application (Academic Press, 2008). Google Scholar
- 2. , Two kinds of generalized 3-connectivities of alternating group networks, in Proc. 12th International Frontiers of Algorithmics Workshop (FAW 2018),
May 8–10 ,Guangzhou, China ,Lecture Notes in Computer Science (2018), pp. 1–23. Crossref, Google Scholar - 3. , The 4-component connectivity of alternating group networks, Theoret. Comput. Sci. (2018). https://doi.org/10.1016/j.tcs.2018.09.018 ISI, Google Scholar
- 4. , Generalized connectivity in graphs, Bull. Bombay Math. Colloq. 2 (1984) 1–6. Google Scholar
- 5. , A comment on the exchanged hypercube, IEEE Trans. Parall. Emerg. Distrib. Process. 16 (2005) 866–874. Crossref, ISI, Google Scholar
- 6. , Conditional matching preclusion sets, Inf. Sci. 179 (2009) 1092–1101. Crossref, ISI, Google Scholar
- 7. , A strong connectivity property of the generalized exchangd hypercube, Discr. Appl. Math. 216 (2017) 529–536. Crossref, ISI, Google Scholar
- 8. , Structural properties of generalized exchanged hypercubes, Emerg. Comput. 24 (2017) 215–232. Google Scholar
- 9. , Connectivity results of hierarchical cubic networks as associated with linearly many faults, in Proc. Int. Symp. Pervasive Systems, Algorithms, and Networks (I-SPAN 2014),
December 19–21, 2014 ,Chengdu, China , pp. 1213–1220. Google Scholar - 10. , Connectivity results of complete cubic networks as associated with linearly many faults, J. Interconnect. Netw. 15 (2015) 155007. Link, ISI, Google Scholar
- 11. , Reliability analysis of twisted cubes, Theoret. Comput. Sci. 707 (2018) 96–101. Crossref, ISI, Google Scholar
- 12. , Fault tolerance of locally twisted cubes, Appl. Math. Comput. 334 (2018) 401–406. Crossref, ISI, Google Scholar
- 13. , Component connectivity of the hypercubes, Inter. J. Comput. Math. 89(2) (2012) 137–145. Crossref, ISI, Google Scholar
- 14. , Efficient algorithms for reliability analysis of distributed computing systems, Infor. Sci. 117 (1999) 89–106. Crossref, ISI, Google Scholar
- 15. , The exchanged hypercube, IEEE Trans. Parall. Emerg. Distrib. Syst. 18 (2007) 576. Crossref, ISI, Google Scholar
- 16. , Connectivity of a graph-a generalization, J. Comb. Inf. Syst. Sci. 9 (1984) 71–78. Google Scholar
- 17. , On the maximal connected component of a hypercube with faulty vertices III, Inter. J. Comput. Math. 83 (2006) 27–37. Crossref, ISI, Google Scholar
- 18. , Two kinds of generalized connectivity of dual cubes, Discr. Appl. Math. (2018). https://doi.org/10.1016/j.dam.2018.09.025 ISI, Google Scholar
- 19. , Component connectivity of hypercubes, Theoret. Comput. Sci. 640 (2016) 115–118. Crossref, ISI, Google Scholar
- 20. , Conditional connectivity of folded hypercubes, Discr. Appl. Math. (2018). https://doi.org/10.1016/j.dam.2018.09.022 ISI, Google Scholar


