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.

On the 3-Extra Connectivity of Enhanced Hypercubes

    Reliability evaluation of interconnection networks is of significant importance to the design and maintenance of interconnection networks. The extra connectivity is an important parameter for the reliability evaluation of interconnection networks. Given a graph G and a positive integer g, the g-extra connectivity, denoted by κg(G), is the minimum cardinality of a set of vertices in G, if exists, whose deletion disconnects G and leaves each remaining component with at least (g+1) vertices. In this paper, we show that the 3-extra connectivity of the (n,k)-enhanced hypercube is (4n5) for n7 and 1kn6. Some previous results in [IEEE Trans. Comput. 63 (2014) 1594–1600] and [Theor. Comput. Sci. 799 (2019) 22–31] are extended.

    Communicated by Sun-Yuan Hsieh

    References

    • 1. J. Xu, Topological Structure and Analysis of Interconnection Networks (Kluwer Academic Publishers, 2001). CrossrefGoogle Scholar
    • 2. J. Fàbrega and M. A. Fiol, On the extraconnectivity of graphs, Discret. Math. 155(1–3) (1996) 49–57. Crossref, ISIGoogle Scholar
    • 3. F. Harary, Conditional connectivity, Networks 13 (1983) 347–357. Crossref, ISIGoogle Scholar
    • 4. W. Yang and J. Meng, Extraconnectivity of hypercubes, Appl. Math. Lett. 22(6) (2009) 887–891. Crossref, ISIGoogle Scholar
    • 5. J. Zhou, On g-extra connectivity of hypercube-like networks, J. Comput. Syst. Sci. 88 (2017) 208–219. Crossref, ISIGoogle Scholar
    • 6. M. Zhang and J. Zhou, On g-extra connectivity of folded hypercubes, Theor. Comput. Sci. 593 (2015) 146–153. Crossref, ISIGoogle Scholar
    • 7. N. Chang, C. Tsai and S. Hsieh, On 3-extra connectivity and 3-extra edge connectivity of folded hypercubes, IEEE Trans. Comput. 63(6) (2014) 1594–1600. Crossref, ISIGoogle Scholar
    • 8. A. Liu, S. Wang, J. Yuan and X. Ma, The h-extra connectivity of k-ary n-cubes, Theoret. Comput. Sci. 784 (2019) 21–45. Crossref, ISIGoogle Scholar
    • 9. J. Li, Y. Huang, L. Lin, H. Yu and R. Chen, The extra connectivity of enhanced hypercubes, Inter. J. Parall. Emer. Distri. Syst. 35(1) (2020) 91–102. Crossref, ISIGoogle Scholar
    • 10. E. Sabir, A. Mamut and E. Vumar, The extra connectivity of the enhanced hypercubes, Theoret. Comput. Sci. 799 (2019) 22–31. Crossref, ISIGoogle Scholar
    • 11. W. Yang, H. Li, On reliability of the folded hypercubes in terms of the extra edge-connectivity, Inf. Sci. 272 (2014) 238–243. Crossref, ISIGoogle Scholar
    • 12. M. Zhang, J. Meng, W. Yang and Y. Tian, Reliability analysis of bijective connection networks in terms of the extra edge-connectivity, Inf. Sci. 279 (2014) 374–382. Crossref, ISIGoogle Scholar
    • 13. M. Zhang, L. Zhang and X. Feng, Reliability measures in relation to the h-extra edge-connectivity of folded hypercubes, Theor. Comput. Sci. 615 (2016) 71–77. Crossref, ISIGoogle Scholar
    • 14. Q. Zhang, L. Xu and W. Yang, Reliability analysis of the augmented cubes in terms of the extra edge-connectivity and the component edge-connectivity, J. Parall. Distrib. Comput. 147 (2021) 124–131. Crossref, ISIGoogle Scholar
    • 15. L. Xu, S. Zhou, J. Liu and S. Yin, Reliability measure of multiprocessor system based on enhanced hypercubes, Discret. Appl. Math. 289 (2021) 125–138. Crossref, ISIGoogle Scholar
    • 16. J. A. Bondy and U. S. R. Murty, Graph Theory (Springer, Berlin, 2008). CrossrefGoogle Scholar
    • 17. L. Lin, S. Hsieh, R. Chen, L. Xu and C. Lee, The relationship between g-restricted connectivity and g-good-neighbor fault diagnosability of general regular networks, IEEE Trans. Reliab. 67(1) (2018) 285–296. Crossref, ISIGoogle Scholar
    • 18. A. El-Amawy and S. Latifi, Properties and performance of folded hypercubes, IEEE Trans. Parall. Distri. Syst. 2(1) (1991) 31–42. Crossref, ISIGoogle Scholar
    • 19. N. Tzeng and S. Wei, Enhanced hypercubes, IEEE Trans. Comput. 40(3) (1991) 284–294. Crossref, ISIGoogle Scholar
    • 20. A. Esfahanian, Generalized measures of fault tolerance with application to n-cube networks, IEEE Trans. Comput. 38(11) (1989) 1586–1591. Crossref, ISIGoogle Scholar
    • 21. D. Wang, Diagnosability of enhanced hypercubes, IEEE Trans Comput. 43(9) (1994) 1054–1061. Crossref, ISIGoogle Scholar
    • 22. H. Liu, Properties of enhanced hypercube networks, J. Syst. Sci. Inf. 3 (2008) 251–256. Google Scholar
    • 23. X. Yang, D. Evans, B. Chen, G. Menson and H. Lai, On the maximal connected component of hypercube with faulty vertices, Inter. J. Comput. Math. 81(5) (2004) 515–525. Crossref, ISIGoogle Scholar
    • 24. D. Yuan and H. Liu, A structural property of enhanced hypercube, Sixth International Conference on Electronics and Information Engineering (2015). Google Scholar
    • 25. Q. Zhu, J. Xu, X. Hou and M. Xu, On reliability of the folded hypercubes, Inf. Sci. 177 (2007) 1782–1788. Crossref, ISIGoogle Scholar