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.

Reliability Analysis of the Generalized Exchanged Hypercube

    Let G=(V(G),E(G)) be a non-complete graph, a subset TV(G) is called a r-component cut of G, if GT is disconnected and has at least r components. The cardinality of the minimum r-component cut is the r-component connectivity of G and is denoted by cκr(G). The r-component connectivity is a natural extension of the classical connectivity. As an application, the r-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 r-component connectivity of the generalized exchanged hypercube GEH(s,t) for 1rs and s2. In this paper, we continue the work and determine that cκs+2(GEH(s,t))=s2+3s21 for s6. Moreover, we show that every optimal r-component cut of GEH(s,t) is trivial for 1rs and s2.

    References

    • 1. J. A. Bondy and U. S. R. Murty, Graph Theory and Its Application (Academic Press, 2008). Google Scholar
    • 2. J.-M. Chang, K.-J. Pai, J.-S. Yang and R.-Y. Ro, 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. CrossrefGoogle Scholar
    • 3. J.-M. Chang, K.-J. Pai, R.-Y. Wu and J.-S. Yang, The 4-component connectivity of alternating group networks, Theoret. Comput. Sci. (2018). https://doi.org/10.1016/j.tcs.2018.09.018 ISIGoogle Scholar
    • 4. G. Chartrand, S. Kapoor, L. Lesniak and D. Lick, Generalized connectivity in graphs, Bull. Bombay Math. Colloq. 2 (1984) 1–6. Google Scholar
    • 5. Y. W. Chen, A comment on the exchanged hypercube, IEEE Trans. Parall. Emerg. Distrib. Process. 16 (2005) 866–874. Crossref, ISIGoogle Scholar
    • 6. E. Cheng, L. Lesniak, M. Lipman and L. Lipták, Conditional matching preclusion sets, Inf. Sci. 179 (2009) 1092–1101. Crossref, ISIGoogle Scholar
    • 7. E. Cheng, K. Qiu and Z. Z. Shen, A strong connectivity property of the generalized exchangd hypercube, Discr. Appl. Math. 216 (2017) 529–536. Crossref, ISIGoogle Scholar
    • 8. E. Cheng, K. Qiu and Z. Z. Shen, Structural properties of generalized exchanged hypercubes, Emerg. Comput. 24 (2017) 215–232. Google Scholar
    • 9. E. Cheng, K. Qiu and Z. Shen, 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. E. Cheng, K. Qiu and Z. Shen, Connectivity results of complete cubic networks as associated with linearly many faults, J. Interconnect. Netw. 15 (2015) 155007. Link, ISIGoogle Scholar
    • 11. L. T. Guo, Reliability analysis of twisted cubes, Theoret. Comput. Sci. 707 (2018) 96–101. Crossref, ISIGoogle Scholar
    • 12. L. T. Guo, G. Su, W. Lin and J. Chen, Fault tolerance of locally twisted cubes, Appl. Math. Comput. 334 (2018) 401–406. Crossref, ISIGoogle Scholar
    • 13. L. H. Hsu, E. Cheng, L. Lipták, J. J. M. Tan, C. K. Lin and T. Y. Ho, Component connectivity of the hypercubes, Inter. J. Comput. Math. 89(2) (2012) 137–145. Crossref, ISIGoogle Scholar
    • 14. M. Lin, M. Chang and D. Chen, Efficient algorithms for reliability analysis of distributed computing systems, Infor. Sci. 117 (1999) 89–106. Crossref, ISIGoogle Scholar
    • 15. P. K. K. Loh, W. J. Hsu and Y. Pan, The exchanged hypercube, IEEE Trans. Parall. Emerg. Distrib. Syst. 18 (2007) 576. Crossref, ISIGoogle Scholar
    • 16. E. Sampathkumar, Connectivity of a graph-a generalization, J. Comb. Inf. Syst. Sci. 9 (1984) 71–78. Google Scholar
    • 17. X. Yang, D. J. Evans and G. M. Megson, On the maximal connected component of a hypercube with faulty vertices III, Inter. J. Comput. Math. 83 (2006) 27–37. Crossref, ISIGoogle Scholar
    • 18. S. L. Zhao, R. X. Hao and E. Cheng, Two kinds of generalized connectivity of dual cubes, Discr. Appl. Math. (2018). https://doi.org/10.1016/j.dam.2018.09.025 ISIGoogle Scholar
    • 19. S. L. Zhao, W. H. Yang and S. R. Zhang, Component connectivity of hypercubes, Theoret. Comput. Sci. 640 (2016) 115–118. Crossref, ISIGoogle Scholar
    • 20. S. L. Zhao and W. H. Yang, Conditional connectivity of folded hypercubes, Discr. Appl. Math. (2018). https://doi.org/10.1016/j.dam.2018.09.022 ISIGoogle Scholar