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.

A Brief Account on the Development and Future Research Directions of Connectivity Properties of Interconnection Networks

    This article is part of the issue:

    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. S. B. Akers and B. Krishnamurthy, A group theoretic model for symmetric interconnection networks, IEEE Transactions on Computers 38(4) (1989) 555–566. Crossref, ISIGoogle Scholar
    • 2. A. Angjeli, E. Cheng and L. Lipták, Linearly many faults in dual-cube-like networks, Theoretical Computer Science 472 (2013) 1–8. Crossref, ISIGoogle Scholar
    • 3. C. A. Barefoot, R. Entringer and H. C. Stwart, Vulnerability in graphs — A comparative survey, Journal of Combinatorial Mathematics and Combinatorial Computing 1 (1986) 13–22. Google Scholar
    • 4. V. Batagelj and M. Zaveršnik, Short cycle connectivity, Discrete Mathematics 307 (2007) 310–318. Crossref, ISIGoogle Scholar
    • 5. D. Bauer, S. L. Hakimi and E. Schmeichel, Recognizing tough graphs is NP-hard, Discrete Applied Mathematics 28 (1990) 191–195. Crossref, ISIGoogle Scholar
    • 6. D. Bauer, H. Broersma and E. Schmeichel, Toughness in graphs — A survey, Graphs and Combinatorics 22 (2006) 1–35. Crossref, ISIGoogle Scholar
    • 7. D. Cheng, 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. CrossrefGoogle Scholar
    • 8. E. Cheng, R.-X. Hao, K. Qiu and Z. Shen, Structural properties and fault resiliency of interconnection networks, in Parallel to Emergent Computing, eds. A. AdamatzkyS. AklG. Sirakoulis (CRC Press, 2019), pp. 77–101. CrossrefGoogle Scholar
    • 9. E. Cheng, P. Hu, R. Jia and L. Lipták, Matching preclusion and conditional matching preclusion for bipartite interconnection networks I: Sufficient conditions, Networks 59 (2012) 349–356. Crossref, ISIGoogle Scholar
    • 10. E. Cheng, L. Lipták, S.-H. Shim and D. Steffy, On the problem of determining which (n, k)-star graphs are Cayley graphs, Graphs and Combinatorics 33 (2017) 85–102. Crossref, ISIGoogle Scholar
    • 11. E. Cheng, W. Lindsey and D. Steffy, Maximal vertex-connectivity of Sn,k, Networks 46 (2000) 154–162. CrossrefGoogle Scholar
    • 12. E. Cheng and M. L. Lipman, Vulnerability issues of star graphs, alternating group graphs and split-stars: Strength and toughness, Discrete Applied Mathematics 118 (2002) 163–179. Crossref, ISIGoogle Scholar
    • 13. E. Cheng and M. L. Lipman, Orienting split-stars and alternating group graphs, Networks 35 (2000) 139–144. Crossref, ISIGoogle Scholar
    • 14. E. Cheng and M. L. Lipman, On the Day-Tripathi orientation of the star graphs: Connectivity, Information Processing Letters 73 (2000) 5–10. Crossref, ISIGoogle Scholar
    • 15. E. Cheng and M. L. Lipman, Orienting the arrangement graphs, Congressus Numerantium 142 (2000) 5–10. Google Scholar
    • 16. E. Cheng and M. L. Lipman, Unidirectional (n, k)-star graphs, Journal of Interconnection Networks 3 (2002) 97–112. LinkGoogle Scholar
    • 17. E. Cheng, M. L. Lipman and L. Lipták, Strong structural properties of unidirectional star graphs, Discrete Applied Mathematics 156 (2008) 2939–2949. Crossref, ISIGoogle Scholar
    • 18. E. Cheng, M. L. Lipman and L. Lipták, Matching preclusion and conditional matching preclusion for regular interconnection networks, Discrete Applied Mathematics 160 (2012) 1936–1954. Crossref, ISIGoogle Scholar
    • 19. E. Cheng and L. Lipták, Structural properties of Cayley graphs generated by transposition trees, Congressus Numerantium 180 (2006) 81–96. Google Scholar
    • 20. E. Cheng and L. Lipták, Fault resiliency of Cayley graphs generated by transpositions, International Journal of Foundations of Computer Science 18 (2007) 1005–1022. Link, ISIGoogle Scholar
    • 21. E. Cheng and L. Lipták, Linearly many faults in Cayley graphs generated by transposition trees, Information Sciences 177 (2007) 4877–4882. Crossref, ISIGoogle Scholar
    • 22. E. Cheng, L. Lipták, K. Qiu and Z. Shen, Cyclic vertex-connectivity of Cayley graphs generated by transposition trees, Graphs and Combinatorics 29 (2013) 835–841. Crossref, ISIGoogle Scholar
    • 23. E. Cheng, L. Lipták and N. Shawash, Orienting Cayley graphs generated by transposition trees, Computers and Mathematics with Applications 55 (2008) 2662–2672. Crossref, ISIGoogle Scholar
    • 24. E. Cheng, L. Lipták, W. Yang, Z. Zhang and X. Guo, A kind of conditional vertex-connectivity of Cayley graphs generated by 2-trees, Information Sciences 181 (2011) 4300–4308. Crossref, ISIGoogle Scholar
    • 25. E. Cheng, L. Lipták and A. Yuan, Linearly many faults in arrangement graphs, Networks 61 (2013) 281–289. Crossref, ISIGoogle Scholar
    • 26. E. Cheng and Y. Mao (Guest Editors), Special Issue on Matching Preclusion, Journal of Interconnection Networks 4 (2019). Google Scholar
    • 27. E. Cheng, K. Qiu and Z. Shen, Connectivity results of complete cubic network as associated with linearly many faults, Journal of Interconnection Networks 15(1 & 2) (2015) 1550007. Link, ISIGoogle Scholar
    • 28. E. Cheng, K. Qiu and Z. Shen, A strong connectivity property of the generalized exchanged hypercube, Discrete Applied Mathematics 216 (2017) 529–536. Crossref, ISIGoogle Scholar
    • 29. E. Cheng, K. Qiu and Z. Shen, 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. CrossrefGoogle Scholar
    • 30. E. Cheng, K. Qiu and Z. Shen, On the restricted connectivity of the arrangement graphs, Journal of Supercomputing 73 (2017) 3669–3682. Crossref, ISIGoogle Scholar
    • 31. E. Cheng, K. Qiu and Z. Shen, On diagnosability of interconnection networks, International Journal of Unconventional Computing 13 (2017) 245–251. ISIGoogle Scholar
    • 32. E. Cheng, K. Qiu and Z. Shen, A general approach to deriving the g-good-neighbor conditional diagnosability of interconnection networks, Theoretical Computer Science 757(24) (2019) 56–67. CrossrefGoogle 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. V. Chvátal, Tough graphs and hamiltonian circuits, Discrete Mathematics 5 (1973) 215–228. CrossrefGoogle Scholar
    • 35. W. H. Cunningham, Optimal attack and reinforcement of a network, Journal of the ACM 32 (1985) 549–561. Crossref, ISIGoogle Scholar
    • 36. T. Dvořák and M.-M. Gu, Neighbor connectivity of k-ary n-cubes, Applied Mathematics and Computation 379 (2020) 125237. Crossref, ISIGoogle Scholar
    • 37. M.-M. Gu, R.-X. Hao and E. Cheng, Strongly Menger connectedness of data center network and (n, k)-star graph, Theoretical Computer Science 799 (2019) 94–103. Crossref, ISIGoogle 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. G. Gunther, Neighbour-connectivity in regular graphs, Discrete Applied Mathematics 11 (1985) 233–243. Crossref, ISIGoogle Scholar
    • 40. D. Gusfield, Connectivity and edge disjoint spanning trees, Information Processing Letters 16 (1983) 87–89. Crossref, ISIGoogle Scholar
    • 41. S. He, R.-X. Hao and E. Cheng, Strongly Menger-edge-connectedness and strongly Menger-vertex-connectedness of regular networks, Theoretical Computer Science 731 (2018) 50–67. Crossref, ISIGoogle Scholar
    • 42. F. Harary, Conditional connectivity, Networks 13 (1983) 347–357. Crossref, ISIGoogle Scholar
    • 43. Y. M. Hong, J. X. Meng and Z. Zhang, Edge fault tolerance of graphs with respect to super edge connectivity, Discrete Applied Mathematics 160 (2012) 579–587. Crossref, ISIGoogle Scholar
    • 44. Y. M. Hong and Z. Zhang, Vertex fault tolerance of optimal-κ graphs and super-κ graphs, Information Processing Letters 109 (2009) 1151–1155. Crossref, ISIGoogle Scholar
    • 45. S.-Y. Hsieh, Private communication. Google Scholar
    • 46. L.-H. Hsu, E. Cheng, L. Lipták, J. J. M. Tan, C.-K. Lin and T.-Y. Ho, Component connectivity of the hypercubes, International Journal of Computer Mathematics 89(2) (2012) 137–145. Crossref, ISIGoogle Scholar
    • 47. X.-J. Li and J.-M. Xu, Generalized measures of fault tolerance in exchanged hypercubes, Information Processing Letters 113 (2013) 533–537. Crossref, ISIGoogle Scholar
    • 48. J. Liang, D. Lou and Z. Zhang, A polynomial time algorithm for cyclic vertex-connectivity of cubic graphs, International Journal of Computer Mathematics 94 (2017) 1501–1514. Crossref, ISIGoogle Scholar
    • 49. C.-K. Lin, L. L. Zhang, J. X. Fan and D. J. Wang, Structure connectivity and substructure connectivity of hypercubes, Theoretical Computer Science 634 (2016) 97–107. Crossref, ISIGoogle Scholar
    • 50. L. Lin, Y. Huang, D. Wang, S.-Y. Hsieh and L. Xu, Novel measurement for network reliability, manuscript. Google Scholar
    • 51. L. Lin, L. Xu and S. Zhou, Relating the extra connectivity and the conditional diagnosability of regular graphs under the comparison model, Theoretical Computer Science 618 (2016) 21–29. Crossref, ISIGoogle Scholar
    • 52. L. Lin, L. Xu, S. Zhou and S.-Y. Hsieh, The extra, restricted connectivity and conditional diagnosability of split-star networks, IEEE Transactions on Parallel and Distributed Systems 27 (2016) 533–545. Crossref, ISIGoogle Scholar
    • 53. R. Lin and H. Zhang, The restricted edge-connectivity and restricted connectivity of augmented k-ary n-cubes, International Journal of Computer Mathematics 92 (2016 1281–1298. CrossrefGoogle Scholar
    • 54. R. Lin and H. Zhang, Maximally matched and super matched regular graphs, International Journal of Computer Mathematics: Computer System Theory 2 (2016) 74–84. CrossrefGoogle Scholar
    • 55. M. J. Lv, S. M. Zhou, X. Sun, L. Li, G. G. Lian and J. F. Liu, Reliability of (n, k)-star network based on g-extra conditional fault, Theoretical Computer Science 757 (2019) 44–55. Crossref, ISIGoogle Scholar
    • 56. M. Ma and L. Zhu, The superconnectivity of exchanged hypercubes, Information Processing Letters 111 (2011) 360–364. Crossref, ISIGoogle Scholar
    • 57. W. Mader, Minimale n-fach zusammenhangende graphen, Mathematische Annalen 191 (1971) 21–28. CrossrefGoogle Scholar
    • 58. Y. Mao, Private communication. Google Scholar
    • 59. C. Melekian and E. Cheng, A note on generalized matching preclusion in bipartite graphs, Theoretical Computer Science 791 (2019) 132–140. Crossref, ISIGoogle Scholar
    • 60. J. X. Meng, Connectivity of vertex and edge-transitive graphs, Discrete Applied Mathematics 127 (2003) 601–613. Crossref, ISIGoogle 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. E. Oh and J. Chen, On strong Menger-connectivity of star graphs, Discrete Applied Mathematics 129 (2003) 499–511. Crossref, ISIGoogle Scholar
    • 63. E. Oh and J. Chen, Strong fault-tolerance: Parallel routing in star networks with faults, Journal of Interconnection Networks 4 (2003) 113–126. LinkGoogle 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. Y.-J. Shang, R.-X. Hao and M.-M. Gu, Neighbor connectivity of two kinds of Cayley graphs, Acta Mathematicae Applicatae Sinica, 34 (2018) 286–397 [English Series]. Crossref, ISIGoogle Scholar
    • 66. K. Sweet, E. Cheng, L. Li, L. Lipták and D. Steffy, A complete classification of which (n, k)-star graphs are Cayley graphs, Graphs and Combinatorics 34 (2018) 241–260. Crossref, ISIGoogle Scholar
    • 67. P. G. Tait, 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. J. Tu, Y. Zhou and G. Su, A kind of conditional connectivity of Cayley graphs generated by wheel graphs, Applied Mathematics and Computation 301 (2017) 177–186. Crossref, ISIGoogle Scholar
    • 71. J. M. Xu and K. L. Xu, On restricted edge-connectivity of graphs, Discrete Mathematics 243 (2002) 291–298. Crossref, ISIGoogle Scholar
    • 72. L. Xu, L. Lin, S. Zhou and S. Hsieh, The extra connectivity, extra conditional diagnosability, and t/m-diagnosability of arrangement graphs, IEEE Transactions on Reliability 65(3) (2016) 1–15. Crossref, ISIGoogle Scholar
    • 73. S. Wang and K. Feng, Fault tolerance in the arrangement graphs, Theoretical Computer Science 533(14) (2014) 64–71. CrossrefGoogle Scholar
    • 74. S. Wang, Z. Wang and M. Wang, The 2-extra connectivity and 2-extra diagnosability of bubble-sort star graph networks, The Computer Journal 59(12) (2016) 1839–1856. Crossref, ISIGoogle Scholar
    • 75. S. Wang and M. Wang, The g-good-neighbor and g-extra diagnosability of networks, Theoretical Computer Science 773(14) (2019) 107–114. CrossrefGoogle Scholar
    • 76. M. E. Watkins, Connectivity of transitive graphs, Journal of Combinatorial Theory 8 (1970) 23–29. CrossrefGoogle Scholar
    • 77. W. Yang and J. Meng, Extraconnectivity of hypercubes, Applied Mathematics Letters 22 (2009) 887–891. Crossref, ISIGoogle Scholar
    • 78. W. Yang, Z. Zhang, C. F. Qin and X. F. Guo, On super 2-restricted and 3-restricted edge-connected vertex transitive graphs, Discrete Mathematics 311 (2011) 2683–2689. Crossref, ISIGoogle Scholar
    • 79. W. Yang, S. Zhao and S. Zhang, Strong Menger connectivity with conditional faults of folded hypercubes, Information Processing Letters 125 (2017) 30–34. Crossref, ISIGoogle Scholar
    • 80. X. Yang, D. J. Evans and G. M. Megson, On the maximal connected component of a hypercube with faulty vertices, International Journal of Computer Mathematics 81(5) (2004) 515–525. Crossref, ISIGoogle Scholar
    • 81. X. Yang, D. J. Evans and G. M. Megson, On the maximal connected component of a hypercube with faulty vertices II, International Journal of Computer Mathematics 81(10) (2004) 1175–1185. Crossref, ISIGoogle Scholar
    • 82. X. Yang, D. J. Evans and G. M. Megson, On the maximal connected component of a hypercube with faulty vertices III, International Journal of Computer Mathematics 83(1) (2006) 27–37. Crossref, ISIGoogle Scholar
    • 83. A. Yuan, E. Cheng and L. Lipták, Linearly many faults in (n, k)-star graphs, International Journal of Foundations of Computer Science 22(7) (2011) 1729–1745. Link, ISIGoogle Scholar
    • 84. A. Yuan, E. Cheng and L. Lipták, Linearly many faults in arrangement graphs, Networks 61(4) (2013) 281–289. Crossref, ISIGoogle Scholar
    • 85. P. Zhang, Private communication. Google Scholar
    • 86. S. Zhao, W. Yang and S. Zhang, Component connectivity of hypercubes, Theoretical Computer Science 640 (2016) 115–118. Crossref, ISIGoogle Scholar
    • 87. J. X. Zhou, Super restricted edge connectivity of regular edge-transitive graphs, Discrete Applied Mathematics 160 (2012) 1248–1252. Crossref, ISIGoogle Scholar
    • 88. J. X. Zhou, On g-extra connectivity of hypercube-like networks, Journal of Computer and System Sciences 88 (2017) 208–219. Crossref, ISIGoogle Scholar
    • 89. S. Zhou, Private communication. Google Scholar
    • 90. Q. Zhu, J. Zhang and L. L. Li, The h-extra connectivity and h-extra conditional diagnosability of bubble-sort star graphs, Discrete Applied Mathematics 251 (2018) 173–184. Crossref, ISIGoogle Scholar