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.

Fault-Tolerant Maximal Local-Edge-Connectivity of Augmented Cubes

    This article is part of the issue:

    An interconnection network is usually modeled as a graph, in which vertices and edges correspond to processors and communication links, respectively. Connectivity is an important metric for fault tolerance of interconnection networks. A connected graph G is said to be maximally local-edge-connected if each pair of vertices u and v of G are connected by min{dG(u),dG(v)} pairwise edge-disjoint paths. In this paper, we show that the n-dimensional augmented cube AQn(n4) is (2n3)-edge-fault-tolerant maximally local-edge-connected and the bound (2n3) is sharp; under the restricted condition that each vertex has at least three fault-free adjacent vertices, AQn(n4) is (6n15)-edge-fault-tolerant maximally local-edge-connected and the bound (6n15) is sharp; and under the restricted condition that each vertex has at least r(r3) fault-free adjacent vertices, AQn(n8) is (2nr4r(r+1)+8)-edge-fault-tolerant maximally local-edge-connected. Furthermore, we show that a k-regular graph G is (k3)-fault-tolerant one-to-many maximally local-connected if G does not contain K2,4 and is super (2k4)-vertex-connected of order 1, a k-regular graph G is (k2)-fault-tolerant one-to-many maximally local-connected if G does not contain K2,3 and is super (2k3)-vertex-connected of order 1.

    References

    • 1. A. Angjeli, E. Cheng and L. Lipták, Linearly many faults in augmented cubes, International Journal of Parallel, Emergent and Distributed Systems 28 (2013) 475–483. CrossrefGoogle Scholar
    • 2. J. A. Bondy and U. S. R. Murty, Graph Theory (Springer, New York, 2008). CrossrefGoogle Scholar
    • 3. H. Cai, H. Liu and M. Lu, Fault-tolerant maximal local-connectivity on Bubble-sort star graphs, Discrete Appl. Math. 181 (2015) 33–40. Crossref, ISIGoogle Scholar
    • 4. Y. C. Chen, M. H. Chen and J. J. M. Tan, Maximally local connectivity and connected components of augmented cubes, Inform. Sci. 273 (2014) 387–392. Crossref, ISIGoogle Scholar
    • 5. E. Cheng and M. J. Lipman, Matching preclusion and conditional matching preclusion for regular interconnection networks, Discrete Appl. Math. 160 (2012) 1936–1954. Crossref, ISIGoogle Scholar
    • 6. Q. Cheng, P. S. Li and M. Xu, Conditional (edge-)fault-tolerant strong Menger (edge) connectivity of folded hypercubes, Theoret. Comput. Sci. 728 (2018) 1–8. Crossref, ISIGoogle Scholar
    • 7. S. A. Choudum and V. Sunitha, Augmented cubes, Networks 40 (2002) 71–84. Crossref, ISIGoogle Scholar
    • 8. S. He, R. X. Hao and E. Cheng, Strongly Menger-edge-connectedness and strongly Menger-vertex-connectedness of regular networks, Theoret. Comput. Sci. 731 (2018) 50–67. Crossref, ISIGoogle Scholar
    • 9. S. Y. Hsieh and Y. R. Cian, Conditional edge-fault Hamiltonicity of augmented cubes, Inform. Sci. 180 (2010) 2596–2617. Crossref, ISIGoogle Scholar
    • 10. P. S. Li and M. Xu, Edge-fault-tolerant edge-bipancyclicity of balanced hypercubes, Appl. Math. Comput. 307 (2017) 180–192. Crossref, ISIGoogle Scholar
    • 11. P. S. Li and M. Xu, Fault-tolerant strong Menger (edge) connectivity and 3-extra edge-connectivity of balanced hypercubes, Theoret. Comput. Sci. 707 (2018) 56–68. Crossref, ISIGoogle Scholar
    • 12. P. S. Li and M. Xu, Edge-fault-tolerant strong Menger edge connectivity on the class of hypercube-like networks, Discrete Appl. Math. 259 (2019) 145–152. Crossref, ISIGoogle Scholar
    • 13. M. Ma, G. Liu and J. M. Xu, The super connectivity of augmented cubes, Inform. Process. Lett. 106 (2008) 59–63. Crossref, ISIGoogle Scholar
    • 14. M. Ma, Y. Song and J. M. Xu, Fault-tolerant analysis of augmented cubes, Mathematics (2012). Google Scholar
    • 15. K. Menger, Zur allgemeinen kurvebtheorie, Fund. Math. 10 (1927) 95–115. CrossrefGoogle Scholar
    • 16. E. Oh and J. Chen, On strong Menger connectivity of star graphs, Discrete Appl. Math. 129 (2003) 499–511. Crossref, ISIGoogle Scholar
    • 17. E. Oh and J. Chen, On strong fault tolerance (or strong Menger connectivity) of multicomputer networks, Ph. D. Thesis, Computer Science Texas A&M University, 2004. Google Scholar
    • 18. E. Oh and J. Chen, On strong fault tolerance: parallel routing in star networks with faults, J. Inter. Net. 4 (2003) 113–126. LinkGoogle Scholar
    • 19. Y. Qiao and W. Yang, Edge disjoint paths in hypercubes and folded hypercubes with conditional faults, Appl. Math. Comput. 294 (2017) 96–101. Crossref, ISIGoogle Scholar
    • 20. L.-M. Shih, C.-F. Chiang, L.-H. Hsu and J.-M. Tan, Fault tolerant maximal local connectivity on Cayley graph generated by transposition tree, J. Inter. Net. 10 (2009) 253–260. LinkGoogle Scholar
    • 21. L.-M. Shih, C.-F. Chiang, L.-H. Hsu and J.-M. Tan, Strong Menger connectivity with conditional faults on the class of hypercube-like networks, Inform. Process. Lett. 106 (2008) 64–69. Crossref, ISIGoogle Scholar
    • 22. L.-M. Shih and J. J. M. Tan, Fault-tolerant maximal local-connectivity on the Bubble-sort graphs, in 6th International Conference on Information Technology: New Generations, 2009, pp. 564–569. Google Scholar
    • 23. W. H. Yang, S. L. Zhao and S. R. Zhang, Strong Menger connectivity with conditional faults of folded hypercubes, Inform. Process. Lett. 125 (2017) 30–34. Crossref, ISIGoogle Scholar
    • 24. S. Zhou and L. Chen, Fault tolerant maximal local connectivity of alternating group networks, in 3rd International Congress on Image and Signal Processing, 2010, pp. 4394–4398. Google Scholar