[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Vulnerability assessment of a new class of Cayley graph

  • Original Research
  • Published:
Journal of Applied Mathematics and Computing Aims and scope Submit manuscript

Abstract

As the number of links and processors in an interconnection network increases, faulty links and processors are constantly emerging. When a network fails, how to evaluate the state of the network and mitigate the vulnerability of the network itself is the focus of attention in recent years. Therefore, the parameters for assessing network vulnerability have received considerable attention. In general, we use connectivity and diagnosability to reflect the vulnerability of the network. At present, the connectivity and diagnosability of most networks have been determined. In this paper, we mainly analyze Cayley graphs \(EC_m\), which are generated by disjoint paths with length 2. We explain that connectivity and super connectivity of \(EC_m\) are uniformly 2m, the 1-extra and 3-component connectivity of \(EC_m\) are uniformly \(4m-2\). In addition, we also analyze the local diagnosability of \(EC_m\) under the PMC and \(\hbox {MM}^*\) models is 2m.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

References

  1. Bondy, J.A., Murthy, U.S.R.: Graph theory with applications. New York (1989)

  2. Oh, A., Choi, H.-A.: Generalized measures of fault tolerance in \(n\)-cube networks. IEEE Trans. Parallel Distrib. Syst. 4, 702–703 (1993)

    Article  MATH  Google Scholar 

  3. Robertson, N.: Minimal cyclic-4-connected graphs. Trans. Am. Math. Soc. 284, 665–684 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  4. Cheng, E., Lipman, M.J.: Increasing the connectivity of the star graphs. Networks 40, 165–169 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  5. Guo, J., Lu, M.: The extra connectivity of bubble-sort star graphs. Theoret. Comput. Sci. 645, 91–99 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  6. Cheng, E., Qiu, K., Shen, Z.: A general approach to deriving the g-good-neighbor conditional diagnosability of interconnection networks. Theoret. Comput. Sci. 757, 56–67 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  7. Chen, D.: A relationship between \(g\)-good-neighbour conditional diagnosability and \(g\)-good-neighbour connectivity in regular graphs. Int. J. Comput. Math. 3, 47–52 (2018)

    MathSciNet  MATH  Google Scholar 

  8. Zhang, H., Zhou, S.: Reliability evaluation of DQcube based on \(g\)-good neighbor and g-component fault pattern. Discret. Appl. Math. 305, 179–190 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  9. Zhang, H., Zhou, S., Cheng, E.: Restricted connectivity of cayley graph generated by transposition trees. Discret. Appl. Math. 327, 87–95 (2023)

    Article  MathSciNet  MATH  Google Scholar 

  10. Zhang, H., Meng, J.: Reliability of DQcube based on \(g\)-extra conditional fault. Comput. J. 64, 1393–1400 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  11. Wang, M., Ren, Y., Lin, Y., Wang, S.: The tightly super 3-extra connectivity and diagnosability of locally twisted cubes. Am. J. Comput. Math. 7, 127–144 (2017)

    Article  MATH  Google Scholar 

  12. Fàbrega, J., Fiol, M.A.: On the extraconnectivity of graphs. Discret. Math. 155, 49–57 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  13. Hsu, L.-H., Cheng, E., Lipták, L., Tan, J.-M., Lin, C.-K., Ho, T.-Y.: Component connectivity of the hypercubes. Int. J. Comput. Math. 89, 137–145 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  14. Zhang, H., Zhou, S.: Component connectivity of alternating group networks and godan graphs. Int. J. Found. Comput. Sci. 34, 395–410 (2023)

    Article  MathSciNet  MATH  Google Scholar 

  15. Zhang, H., Zhou, S., Liu, X., Yu, Z.: Extra (component) connectivity and diagnosability of bubble sort networks. Theoret. Comput. Sci. 940, 180–189 (2023)

    Article  MathSciNet  MATH  Google Scholar 

  16. Zhang, H., Zhou, S., Zhang, Q., Tian, T.: Fault tolerance of composite graph based on disc-ring and folded hypercube. Theoret. Comput. Sci. 958, 113856 (2023)

    Article  MathSciNet  MATH  Google Scholar 

  17. Chang, J.-M., Pai, K.-J., Wu, R.-R., Yang, J.-S.: The 4-component connectivity of alternating group networks. Theoret. Comput. Sci. 766, 38–45 (2019)

    Article  MathSciNet  MATH  Google Scholar 

  18. Gu, M.-M., Hao, R.-X., Tang, S.-M., Chang, J.-M.: Analysis on component connectivity of bubble-sort star graphs and burnt pancake graphs. Discret. Appl. Math. 279, 80–91 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  19. Wang, M., Lin, Y., Wang, S.: The nature diagnosability of bubble-sort star graphs under the PMC model and \(\text{ MM}^\ast \) model. Int. J. Eng. Appl. Sci. 4, 2394–3661 (2017)

    MATH  Google Scholar 

  20. Wang, M., Xiang, D., Qu, Y., Li, G.: The diagnosability of interconnection networks. Discret. Appl. Math. 357, 413–428 (2024)

    Article  MathSciNet  MATH  Google Scholar 

  21. Maeng, J., Malek, M.: A comparison connection assignment for self-diagnosis of multiprocessor systems. In: Proceedings of 11th International Symposium on Fault-Tolerant Computing, 173-175 (1981)

  22. Sengupta, A., Dahbura, A.T.: On self-diagnosable multiprocessor systems: diagnosis by the comparison approach. IEEE Trans. Comput. 41, 1386–1396 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  23. Preparata, F.P., Metze, G., Chien, R.T.: On the connection assignment problem of diagnosable systems. IEEE Transactions on Computers EC-16, 848-854 (1967)

  24. Akers, S.B., Harel, D.,Krishnamurthy, B.: The star-graph: An attractive alternative to the n-cube. Proc. Internat. Conf. on Parallel Processing, 393-400(1987)

  25. Akers, S.B., Krishnamurthy, B.: Group graphs as interconnection networks. Proc. Fourteenth Internat. Conf. on Fault-Tolerant Computing, 422-427(1984)

  26. Akers, S.B., Krishnamurthy, B.: A group-theoretic model for symmetric interconnection networks. IEEE Trans. Comput. 38, 555–565 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  27. Jwo, J., Lakshmivarahan, S., Dhall, S.K.: A new class of interconnection networks based on the alternatinggroup. Network 23, 315–326 (1993)

    Article  MATH  Google Scholar 

  28. Lakshmivarahan, S., Jwo, J., Dhall, S.K.: Symmetry in interconnection networks based on cayley graphs of permutation groups: a Survey. Parallel Comput. 19, 361–407 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  29. Cheng, E., Lipták, L.: Structural properties of cayley graphs generated by transposition trees. Congr. Numer. 180, 81–96 (2006)

    MathSciNet  MATH  Google Scholar 

  30. Cheng, E., Lipman, M., Lipták, L.: Strong structural properties of unidirectional star graphs. Discret. Appl. Math. 156, 2939–2949 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  31. Li, H., Yang, W., Meng, J.: Fault-tolerant Hamiltonian laceability of cayley graphs generated by transposition trees. Discret. Math. 312, 3087–3095 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  32. Xu, J.-M.: Combinational theory in networks. Science Press, Beijing (2013)

    MATH  Google Scholar 

  33. Zhou, S., Dong, Q.: Reliability analysis of multiprocessor systems. Science Press, Beijing (2020)

    MATH  Google Scholar 

  34. Hsu, G.-H., Tan, J.J.: A local diagnosiability measure for multiprocessor systems. IEEE Trans. Parallel Distrib. Syst. 18, 598–607 (2007)

    Article  MATH  Google Scholar 

  35. Dahbura, A.T., Masson, G.M.: An \(o(n^{2.5})\) fault identification algorithm for diagnosable systems. IEEE Trans. Comput. 33, 486–492 (1984)

    Article  MATH  Google Scholar 

  36. Chiang, C.-F., Tan, J.M.: Using node diagnosability to determine \(t\)-diagnosability under the comparison diagnosis model. IEEE Trans. Comput. 58, 251–259 (2009)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

This work was partly supported by the National Natural Science Foundation of China (Nos. 12361072), 2023 Xinjiang Natural Science Foundation General Project (Nos. 2023D01A36), 2023 Xinjiang Natural Science Foundation For Youths (2023D01B48). This work was also partly supported by 2022 Special Foundation for innovation Team Xinjiang Normal University (Nos. 2022XJNU).

Author information

Author notes

  1. Hong Bian have contributed equally to this work.

Authors and Affiliations

  1. School of Mathematical Sciences, Xinjiang Normal University, Urumqi, 830046, China

    Hong Zhang & Hong Bian

Authors
  1. Hong Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hong Bian
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hong Zhang.

Ethics declarations

Declaration of Conflict of interest

The authors declare no Conflict of interest in this work.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zhang, H., Bian, H. Vulnerability assessment of a new class of Cayley graph. J. Appl. Math. Comput. 71, 969–982 (2025). https://doi.org/10.1007/s12190-024-02270-6

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12190-024-02270-6

Keywords