Fault-Tolerant Maximal Local-Edge-Connectivity of Augmented Cubes
Abstract
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 is said to be maximally local-edge-connected if each pair of vertices and of are connected by pairwise edge-disjoint paths. In this paper, we show that the -dimensional augmented cube is -edge-fault-tolerant maximally local-edge-connected and the bound is sharp; under the restricted condition that each vertex has at least three fault-free adjacent vertices, is -edge-fault-tolerant maximally local-edge-connected and the bound is sharp; and under the restricted condition that each vertex has at least fault-free adjacent vertices, is -edge-fault-tolerant maximally local-edge-connected. Furthermore, we show that a -regular graph is -fault-tolerant one-to-many maximally local-connected if does not contain and is super -vertex-connected of order 1, a -regular graph is -fault-tolerant one-to-many maximally local-connected if does not contain and is super -vertex-connected of order 1.
References
- 1. , Linearly many faults in augmented cubes, International Journal of Parallel, Emergent and Distributed Systems 28 (2013) 475–483. Crossref, Google Scholar
- 2. , Graph Theory (Springer, New York, 2008). Crossref, Google Scholar
- 3. , Fault-tolerant maximal local-connectivity on Bubble-sort star graphs, Discrete Appl. Math. 181 (2015) 33–40. Crossref, ISI, Google Scholar
- 4. , Maximally local connectivity and connected components of augmented cubes, Inform. Sci. 273 (2014) 387–392. Crossref, ISI, Google Scholar
- 5. , Matching preclusion and conditional matching preclusion for regular interconnection networks, Discrete Appl. Math. 160 (2012) 1936–1954. Crossref, ISI, Google Scholar
- 6. , Conditional (edge-)fault-tolerant strong Menger (edge) connectivity of folded hypercubes, Theoret. Comput. Sci. 728 (2018) 1–8. Crossref, ISI, Google Scholar
- 7. , Augmented cubes, Networks 40 (2002) 71–84. Crossref, ISI, Google Scholar
- 8. , Strongly Menger-edge-connectedness and strongly Menger-vertex-connectedness of regular networks, Theoret. Comput. Sci. 731 (2018) 50–67. Crossref, ISI, Google Scholar
- 9. , Conditional edge-fault Hamiltonicity of augmented cubes, Inform. Sci. 180 (2010) 2596–2617. Crossref, ISI, Google Scholar
- 10. , Edge-fault-tolerant edge-bipancyclicity of balanced hypercubes, Appl. Math. Comput. 307 (2017) 180–192. Crossref, ISI, Google Scholar
- 11. , Fault-tolerant strong Menger (edge) connectivity and 3-extra edge-connectivity of balanced hypercubes, Theoret. Comput. Sci. 707 (2018) 56–68. Crossref, ISI, Google Scholar
- 12. , Edge-fault-tolerant strong Menger edge connectivity on the class of hypercube-like networks, Discrete Appl. Math. 259 (2019) 145–152. Crossref, ISI, Google Scholar
- 13. , The super connectivity of augmented cubes, Inform. Process. Lett. 106 (2008) 59–63. Crossref, ISI, Google Scholar
- 14. M. Ma, Y. Song and J. M. Xu, Fault-tolerant analysis of augmented cubes, Mathematics (2012). Google Scholar
- 15. , Zur allgemeinen kurvebtheorie, Fund. Math. 10 (1927) 95–115. Crossref, Google Scholar
- 16. , On strong Menger connectivity of star graphs, Discrete Appl. Math. 129 (2003) 499–511. Crossref, ISI, Google 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. , On strong fault tolerance: parallel routing in star networks with faults, J. Inter. Net. 4 (2003) 113–126. Link, Google Scholar
- 19. , Edge disjoint paths in hypercubes and folded hypercubes with conditional faults, Appl. Math. Comput. 294 (2017) 96–101. Crossref, ISI, Google Scholar
- 20. , Fault tolerant maximal local connectivity on Cayley graph generated by transposition tree, J. Inter. Net. 10 (2009) 253–260. Link, Google Scholar
- 21. , Strong Menger connectivity with conditional faults on the class of hypercube-like networks, Inform. Process. Lett. 106 (2008) 64–69. Crossref, ISI, Google Scholar
- 22. , 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. , Strong Menger connectivity with conditional faults of folded hypercubes, Inform. Process. Lett. 125 (2017) 30–34. Crossref, ISI, Google Scholar
- 24. , Fault tolerant maximal local connectivity of alternating group networks, in 3rd International Congress on Image and Signal Processing,
2010 , pp. 4394–4398. Google Scholar


