Structure and Substructure Connectivity of Hypercube-Like Networks
Abstract
The connectivity of a graph , , is the minimum number of vertices whose removal disconnects , and the value of can be determined using Menger’s theorem. It has long been one of the most important factors that characterize both graph reliability and fault tolerability. Two extensions to the classic notion of connectivity were introduced recently: structure connectivity and substructure connectivity. Let be isomorphic to any connected subgraph of . The -structure connectivity of , denoted by , is the cardinality of a minimum set of connected subgraphs in such that every element of is isomorphic to , and the removal of disconnects . The -substructure connectivity of , denoted by , is the cardinality of a minimum set of connected subgraphs in whose removal disconnects and every element of is isomorphic to a connected subgraph of . The family of hypercube-like networks includes many well-defined network architectures, such as hypercubes, crossed cubes, twisted cubes, and so on. In this paper, both the structure and substructure connectivity of hypercube-like networks are studied with respect to the -star structure, , and the -cycle structure. Moreover, we consider the relationships between these parameters and other concepts.
References
- 1. , The twisted cube topology for multiprocessors: A study in networks asymmetry, Journal of Parallel and Distributed Computing 13 (1991) 104–110. Crossref, ISI, Google Scholar
- 2. , Graph Theory (Springer, London, 2008). Crossref, Google Scholar
- 3. , Restricted connectivity for three families of interconnection networks, Applied Mathematics and Computation 188 (2007) 1848–1855. Crossref, ISI, Google Scholar
- 4. , Hyper Petersen network: Yet another hypercube-like topology, in The Fourth Symposium on the Frontiers of Massively Parallel Computation
(1992) ,McLean, VA, USA , pp. 270–277. Google Scholar - 5. , The crossed cube architecture for parallel computing, IEEE Transactions on Parallel and Distributed Systems 3 (1992) 513–524. Crossref, ISI, Google Scholar
- 6. , Generalized measures of fault tolerance with application to n-cube networks, IEEE Trans. Comput. 38(11) (1989) 1586–1591. Crossref, ISI, Google Scholar
- 7. , On the extraconnectivity of graphs, Discrete Mathematics 155 (1996) 49–57. Crossref, ISI, Google Scholar
- 8. , Conditional connectivity, Networks 13(3) (1983) 347–357. Crossref, ISI, Google Scholar
- 9. , A survey of the theory of hypercube graphs, Computer and Mathematics with Applications 15 (1988) 277–289. Crossref, ISI, Google Scholar
- 10. , Graph Theory and Interconnection Networks (CRC Press, 2008). Crossref, Google Scholar
- 11. , Conditional connectivity measures for large multiprocessor systems, IEEE Transactions on Computers 43(2) (1994) 218–222. Crossref, ISI, Google Scholar
- 12. , Introduction to Parallel Algorithms and Architectures: Arrays ⋅ Trees ⋅ Hypercubes (Morgan Kaufmann, San Mateo, 1992). Google Scholar
- 13. , Structure connectivity and substructure connectivity of hypercubes, Theoretical Computer Science 634 (2016) 97–107. Crossref, ISI, Google Scholar
- 14. , Structure connectivity and substructure connectivity of k-ary n-cube networks, Information Sciences 433-434 (2018) 115–124. Crossref, ISI, Google Scholar
- 15. , Topological properties of hypercubes, IEEE Transactions on Computers 37 (1988) 867–872. Crossref, ISI, Google Scholar
- 16. , Structure fault tolerance of hypercubes and folded hypercubes, Theoretical Computer Science 711 (2018) 44–55. Crossref, ISI, Google Scholar
- 17. , A class of hypercube-like networks, in Proceedings of the Fifth IEEE Symposium on Parallel and Distributed Processing (IEEE Computer Society Press, Los Alamitos, CA, 1993), pp. 800–803. Crossref, Google Scholar
- 18. , Topological Structure and Analysis of Interconnection Networks (Kluwer Academic Publishers, Dordrecht/Boston/London, 2001). Crossref, Google Scholar
- 19. , The locally twisted cubes, International Journal of Computer Mathematics 82 (2005) 401–413. Crossref, ISI, Google Scholar
- 20. , On the maximal connected component of a hypercube with faulty vertices III, International Journal of Computer Mathematics 83 (2006) 27–37. Crossref, ISI, Google Scholar


