World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

Structure and Substructure Connectivity of Hypercube-Like Networks

    This article is part of the issue:

    The connectivity of a graph G, κ(G), is the minimum number of vertices whose removal disconnects G, and the value of κ(G) 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 H be isomorphic to any connected subgraph of G. The H-structure connectivity of G, denoted by κ(G;H), is the cardinality of a minimum set F of connected subgraphs in G such that every element of F is isomorphic to H, and the removal of F disconnects G. The H-substructure connectivity of G, denoted by κ(G;H), is the cardinality of a minimum set X of connected subgraphs in G whose removal disconnects G and every element of X is isomorphic to a connected subgraph of H. 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 m-star K1,m structure, m1, and the 4-cycle C4 structure. Moreover, we consider the relationships between these parameters and other concepts.

    References

    • 1. S. Abraham and K. Padmanabhan, The twisted cube topology for multiprocessors: A study in networks asymmetry, Journal of Parallel and Distributed Computing 13 (1991) 104–110. Crossref, ISIGoogle Scholar
    • 2. J. A. Bondy and U. S. R. Murty, Graph Theory (Springer, London, 2008). CrossrefGoogle Scholar
    • 3. Y-C. Chen and J. J. M. Tan, Restricted connectivity for three families of interconnection networks, Applied Mathematics and Computation 188 (2007) 1848–1855. Crossref, ISIGoogle Scholar
    • 4. S. K. Das and A. K. Banerjee, 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. K. Efe, The crossed cube architecture for parallel computing, IEEE Transactions on Parallel and Distributed Systems 3 (1992) 513–524. Crossref, ISIGoogle Scholar
    • 6. A. H. Esfahanian, Generalized measures of fault tolerance with application to n-cube networks, IEEE Trans. Comput. 38(11) (1989) 1586–1591. Crossref, ISIGoogle Scholar
    • 7. J. Fábrega and M. A. Fiol, On the extraconnectivity of graphs, Discrete Mathematics 155 (1996) 49–57. Crossref, ISIGoogle Scholar
    • 8. F. Harary, Conditional connectivity, Networks 13(3) (1983) 347–357. Crossref, ISIGoogle Scholar
    • 9. F. Harary, J. P. Hayes and H.-J. Wu, A survey of the theory of hypercube graphs, Computer and Mathematics with Applications 15 (1988) 277–289. Crossref, ISIGoogle Scholar
    • 10. L.-H. Hsu and C.-K. Lin, Graph Theory and Interconnection Networks (CRC Press, 2008). CrossrefGoogle Scholar
    • 11. S. Latifi, M. Hegde and M. N. Pour, Conditional connectivity measures for large multiprocessor systems, IEEE Transactions on Computers 43(2) (1994) 218–222. Crossref, ISIGoogle Scholar
    • 12. F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays ⋅ Trees ⋅ Hypercubes (Morgan Kaufmann, San Mateo, 1992). Google Scholar
    • 13. C.-K. Lin, L. Zhang, J. Fan and D. Wang, Structure connectivity and substructure connectivity of hypercubes, Theoretical Computer Science 634 (2016) 97–107. Crossref, ISIGoogle Scholar
    • 14. Y. Lv, J. Fan, D. F. Hsu and C.-K. Lin, Structure connectivity and substructure connectivity of k-ary n-cube networks, Information Sciences 433-434 (2018) 115–124. Crossref, ISIGoogle Scholar
    • 15. Y. Saad and M. H. Schultz, Topological properties of hypercubes, IEEE Transactions on Computers 37 (1988) 867–872. Crossref, ISIGoogle Scholar
    • 16. E. Sabir and J. Meng, Structure fault tolerance of hypercubes and folded hypercubes, Theoretical Computer Science 711 (2018) 44–55. Crossref, ISIGoogle Scholar
    • 17. A. S. Vaidya, P. S. N. Rao and S. R. Shankar, 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. CrossrefGoogle Scholar
    • 18. J.-M. Xu, Topological Structure and Analysis of Interconnection Networks (Kluwer Academic Publishers, Dordrecht/Boston/London, 2001). CrossrefGoogle Scholar
    • 19. X. Yang, D. J. Evans and G. M. Megson, The locally twisted cubes, International Journal of Computer Mathematics 82 (2005) 401–413. Crossref, ISIGoogle Scholar
    • 20. X. Yang, D. J. Evans and G. M. Megson, On the maximal connected component of a hypercube with faulty vertices III, International Journal of Computer Mathematics 83 (2006) 27–37. Crossref, ISIGoogle Scholar