A Brief Account on the Development and Future Research Directions of Connectivity Properties of Interconnection Networks
Abstract
Connectivity type measures form an important topic in graph theory. Such measures provide an important part of analyzing the vulnerability and resilience of interconnection networks. In this short commentary, we outline our perspective on the development of this topic with respect to interconnection networks.
References
- 1. , A group theoretic model for symmetric interconnection networks, IEEE Transactions on Computers 38(4) (1989) 555–566. Crossref, ISI, Google Scholar
- 2. , Linearly many faults in dual-cube-like networks, Theoretical Computer Science 472 (2013) 1–8. Crossref, ISI, Google Scholar
- 3. , Vulnerability in graphs — A comparative survey, Journal of Combinatorial Mathematics and Combinatorial Computing 1 (1986) 13–22. Google Scholar
- 4. , Short cycle connectivity, Discrete Mathematics 307 (2007) 310–318. Crossref, ISI, Google Scholar
- 5. , Recognizing tough graphs is NP-hard, Discrete Applied Mathematics 28 (1990) 191–195. Crossref, ISI, Google Scholar
- 6. , Toughness in graphs — A survey, Graphs and Combinatorics 22 (2006) 1–35. Crossref, ISI, Google Scholar
- 7. , A relationship between g-good-neighbour conditional diagnosability and g-good-neighbour connectivity in regular graphs, International Journal of Computer Mathematics: Computer Systems Theory 3(1) (2018) 47–52. Crossref, Google Scholar
- 8. ,
Structural properties and fault resiliency of interconnection networks , in Parallel to Emergent Computing, eds. A. AdamatzkyS. AklG. Sirakoulis (CRC Press, 2019), pp. 77–101. Crossref, Google Scholar - 9. , Matching preclusion and conditional matching preclusion for bipartite interconnection networks I: Sufficient conditions, Networks 59 (2012) 349–356. Crossref, ISI, Google Scholar
- 10. , On the problem of determining which (n, k)-star graphs are Cayley graphs, Graphs and Combinatorics 33 (2017) 85–102. Crossref, ISI, Google Scholar
- 11. , Maximal vertex-connectivity of , Networks 46 (2000) 154–162. Crossref, Google Scholar
- 12. , Vulnerability issues of star graphs, alternating group graphs and split-stars: Strength and toughness, Discrete Applied Mathematics 118 (2002) 163–179. Crossref, ISI, Google Scholar
- 13. , Orienting split-stars and alternating group graphs, Networks 35 (2000) 139–144. Crossref, ISI, Google Scholar
- 14. , On the Day-Tripathi orientation of the star graphs: Connectivity, Information Processing Letters 73 (2000) 5–10. Crossref, ISI, Google Scholar
- 15. , Orienting the arrangement graphs, Congressus Numerantium 142 (2000) 5–10. Google Scholar
- 16. , Unidirectional (n, k)-star graphs, Journal of Interconnection Networks 3 (2002) 97–112. Link, Google Scholar
- 17. , Strong structural properties of unidirectional star graphs, Discrete Applied Mathematics 156 (2008) 2939–2949. Crossref, ISI, Google Scholar
- 18. , Matching preclusion and conditional matching preclusion for regular interconnection networks, Discrete Applied Mathematics 160 (2012) 1936–1954. Crossref, ISI, Google Scholar
- 19. , Structural properties of Cayley graphs generated by transposition trees, Congressus Numerantium 180 (2006) 81–96. Google Scholar
- 20. , Fault resiliency of Cayley graphs generated by transpositions, International Journal of Foundations of Computer Science 18 (2007) 1005–1022. Link, ISI, Google Scholar
- 21. , Linearly many faults in Cayley graphs generated by transposition trees, Information Sciences 177 (2007) 4877–4882. Crossref, ISI, Google Scholar
- 22. , Cyclic vertex-connectivity of Cayley graphs generated by transposition trees, Graphs and Combinatorics 29 (2013) 835–841. Crossref, ISI, Google Scholar
- 23. , Orienting Cayley graphs generated by transposition trees, Computers and Mathematics with Applications 55 (2008) 2662–2672. Crossref, ISI, Google Scholar
- 24. , A kind of conditional vertex-connectivity of Cayley graphs generated by 2-trees, Information Sciences 181 (2011) 4300–4308. Crossref, ISI, Google Scholar
- 25. , Linearly many faults in arrangement graphs, Networks 61 (2013) 281–289. Crossref, ISI, Google Scholar
- 26. E. Cheng and Y. Mao (Guest Editors), Special Issue on Matching Preclusion, Journal of Interconnection Networks 4 (2019). Google Scholar
- 27. , Connectivity results of complete cubic network as associated with linearly many faults, Journal of Interconnection Networks 15(1 & 2) (2015) 1550007. Link, ISI, Google Scholar
- 28. , A strong connectivity property of the generalized exchanged hypercube, Discrete Applied Mathematics 216 (2017) 529–536. Crossref, ISI, Google Scholar
- 29. ,
Structural properties of the generalized exchanged hypercubes , in Emergent Computation: Emergence, Complexity, Computation, Vol. 24, ed. A. Adamatzky, (Springer, Cham, Switzerland, 2017), pp. 215–232. Crossref, Google Scholar - 30. , On the restricted connectivity of the arrangement graphs, Journal of Supercomputing 73 (2017) 3669–3682. Crossref, ISI, Google Scholar
- 31. , On diagnosability of interconnection networks, International Journal of Unconventional Computing 13 (2017) 245–251. ISI, Google Scholar
- 32. , A general approach to deriving the g-good-neighbor conditional diagnosability of interconnection networks, Theoretical Computer Science 757(24) (2019) 56–67. Crossref, Google Scholar
- 33. E. Cheng, K. Qiu and Z. Shen (Guest Editors), Diagnosability of Interconnection Networks, International Journal of Parallel, Emergent and Distributed Systems 35 (2020). Google Scholar
- 34. , Tough graphs and hamiltonian circuits, Discrete Mathematics 5 (1973) 215–228. Crossref, Google Scholar
- 35. , Optimal attack and reinforcement of a network, Journal of the ACM 32 (1985) 549–561. Crossref, ISI, Google Scholar
- 36. , Neighbor connectivity of k-ary n-cubes, Applied Mathematics and Computation 379 (2020) 125237. Crossref, ISI, Google Scholar
- 37. , Strongly Menger connectedness of data center network and (n, k)-star graph, Theoretical Computer Science 799 (2019) 94–103. Crossref, ISI, Google Scholar
- 38. Gu, M.-M., He, S., Hao, R.-X., Cheng, E., Note on Applications of Linearly Many Faults, The Computer Journal, to appear, https://doi.org/10.1093/comjnl/bxz088. Google Scholar
- 39. , Neighbour-connectivity in regular graphs, Discrete Applied Mathematics 11 (1985) 233–243. Crossref, ISI, Google Scholar
- 40. , Connectivity and edge disjoint spanning trees, Information Processing Letters 16 (1983) 87–89. Crossref, ISI, Google Scholar
- 41. , Strongly Menger-edge-connectedness and strongly Menger-vertex-connectedness of regular networks, Theoretical Computer Science 731 (2018) 50–67. Crossref, ISI, Google Scholar
- 42. , Conditional connectivity, Networks 13 (1983) 347–357. Crossref, ISI, Google Scholar
- 43. , Edge fault tolerance of graphs with respect to super edge connectivity, Discrete Applied Mathematics 160 (2012) 579–587. Crossref, ISI, Google Scholar
- 44. , Vertex fault tolerance of optimal- graphs and super- graphs, Information Processing Letters 109 (2009) 1151–1155. Crossref, ISI, Google Scholar
- 45. S.-Y. Hsieh, Private communication. Google Scholar
- 46. , Component connectivity of the hypercubes, International Journal of Computer Mathematics 89(2) (2012) 137–145. Crossref, ISI, Google Scholar
- 47. , Generalized measures of fault tolerance in exchanged hypercubes, Information Processing Letters 113 (2013) 533–537. Crossref, ISI, Google Scholar
- 48. , A polynomial time algorithm for cyclic vertex-connectivity of cubic graphs, International Journal of Computer Mathematics 94 (2017) 1501–1514. Crossref, ISI, Google Scholar
- 49. , Structure connectivity and substructure connectivity of hypercubes, Theoretical Computer Science 634 (2016) 97–107. Crossref, ISI, Google Scholar
- 50. L. Lin, Y. Huang, D. Wang, S.-Y. Hsieh and L. Xu, Novel measurement for network reliability, manuscript. Google Scholar
- 51. , Relating the extra connectivity and the conditional diagnosability of regular graphs under the comparison model, Theoretical Computer Science 618 (2016) 21–29. Crossref, ISI, Google Scholar
- 52. , The extra, restricted connectivity and conditional diagnosability of split-star networks, IEEE Transactions on Parallel and Distributed Systems 27 (2016) 533–545. Crossref, ISI, Google Scholar
- 53. , The restricted edge-connectivity and restricted connectivity of augmented k-ary n-cubes, International Journal of Computer Mathematics 92 (2016 1281–1298. Crossref, Google Scholar
- 54. , Maximally matched and super matched regular graphs, International Journal of Computer Mathematics: Computer System Theory 2 (2016) 74–84. Crossref, Google Scholar
- 55. , Reliability of (n, k)-star network based on g-extra conditional fault, Theoretical Computer Science 757 (2019) 44–55. Crossref, ISI, Google Scholar
- 56. , The superconnectivity of exchanged hypercubes, Information Processing Letters 111 (2011) 360–364. Crossref, ISI, Google Scholar
- 57. , Minimale n-fach zusammenhangende graphen, Mathematische Annalen 191 (1971) 21–28. Crossref, Google Scholar
- 58. Y. Mao, Private communication. Google Scholar
- 59. , A note on generalized matching preclusion in bipartite graphs, Theoretical Computer Science 791 (2019) 132–140. Crossref, ISI, Google Scholar
- 60. , Connectivity of vertex and edge-transitive graphs, Discrete Applied Mathematics 127 (2003) 601–613. Crossref, ISI, Google Scholar
- 61. E. Oh, On strong fault tolerance (or strong Menger-connectivity) of multicomputer networks, Ph.D. thesis, Computer Science A&M University (August 2004). Google Scholar
- 62. , On strong Menger-connectivity of star graphs, Discrete Applied Mathematics 129 (2003) 499–511. Crossref, ISI, Google Scholar
- 63. , Strong fault-tolerance: Parallel routing in star networks with faults, Journal of Interconnection Networks 4 (2003) 113–126. Link, Google Scholar
- 64. E. Sabir and J. X. Meng, Structure fault tolerance of recursive interconnection networks, The Computer Journal to appear, https://doi.org/10.1093/comjnl/bxz159. Google Scholar
- 65. , Neighbor connectivity of two kinds of Cayley graphs, Acta Mathematicae Applicatae Sinica, 34 (2018) 286–397 [English Series]. Crossref, ISI, Google Scholar
- 66. , A complete classification of which (n, k)-star graphs are Cayley graphs, Graphs and Combinatorics 34 (2018) 241–260. Crossref, ISI, Google Scholar
- 67. , Remarks on the colouring of maps, in Proceedings of the Royal Society of Edinburgh, 17 (1884), 85–98. Google Scholar
- 68. P. G. Tait, Listing’s topologie, Philosophical Magazine, 5th Series, 10 (1880), 501–503. Google Scholar
- 69. R. Tindell, Edge connectivity properties of symmetric graphs, Hoboken: Stevens Institute of Technology (1982). Google Scholar
- 70. , A kind of conditional connectivity of Cayley graphs generated by wheel graphs, Applied Mathematics and Computation 301 (2017) 177–186. Crossref, ISI, Google Scholar
- 71. , On restricted edge-connectivity of graphs, Discrete Mathematics 243 (2002) 291–298. Crossref, ISI, Google Scholar
- 72. , The extra connectivity, extra conditional diagnosability, and t/m-diagnosability of arrangement graphs, IEEE Transactions on Reliability 65(3) (2016) 1–15. Crossref, ISI, Google Scholar
- 73. , Fault tolerance in the arrangement graphs, Theoretical Computer Science 533(14) (2014) 64–71. Crossref, Google Scholar
- 74. , The 2-extra connectivity and 2-extra diagnosability of bubble-sort star graph networks, The Computer Journal 59(12) (2016) 1839–1856. Crossref, ISI, Google Scholar
- 75. , The g-good-neighbor and g-extra diagnosability of networks, Theoretical Computer Science 773(14) (2019) 107–114. Crossref, Google Scholar
- 76. , Connectivity of transitive graphs, Journal of Combinatorial Theory 8 (1970) 23–29. Crossref, Google Scholar
- 77. , Extraconnectivity of hypercubes, Applied Mathematics Letters 22 (2009) 887–891. Crossref, ISI, Google Scholar
- 78. , On super 2-restricted and 3-restricted edge-connected vertex transitive graphs, Discrete Mathematics 311 (2011) 2683–2689. Crossref, ISI, Google Scholar
- 79. , Strong Menger connectivity with conditional faults of folded hypercubes, Information Processing Letters 125 (2017) 30–34. Crossref, ISI, Google Scholar
- 80. , On the maximal connected component of a hypercube with faulty vertices, International Journal of Computer Mathematics 81(5) (2004) 515–525. Crossref, ISI, Google Scholar
- 81. , On the maximal connected component of a hypercube with faulty vertices II, International Journal of Computer Mathematics 81(10) (2004) 1175–1185. Crossref, ISI, Google Scholar
- 82. , On the maximal connected component of a hypercube with faulty vertices III, International Journal of Computer Mathematics 83(1) (2006) 27–37. Crossref, ISI, Google Scholar
- 83. , Linearly many faults in (n, k)-star graphs, International Journal of Foundations of Computer Science 22(7) (2011) 1729–1745. Link, ISI, Google Scholar
- 84. , Linearly many faults in arrangement graphs, Networks 61(4) (2013) 281–289. Crossref, ISI, Google Scholar
- 85. P. Zhang, Private communication. Google Scholar
- 86. , Component connectivity of hypercubes, Theoretical Computer Science 640 (2016) 115–118. Crossref, ISI, Google Scholar
- 87. , Super restricted edge connectivity of regular edge-transitive graphs, Discrete Applied Mathematics 160 (2012) 1248–1252. Crossref, ISI, Google Scholar
- 88. , On g-extra connectivity of hypercube-like networks, Journal of Computer and System Sciences 88 (2017) 208–219. Crossref, ISI, Google Scholar
- 89. S. Zhou, Private communication. Google Scholar
- 90. , The h-extra connectivity and h-extra conditional diagnosability of bubble-sort star graphs, Discrete Applied Mathematics 251 (2018) 173–184. Crossref, ISI, Google Scholar


