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

The edge fault-tolerant spanning laceability of the enhanced hypercube networks

  • Published:
The Journal of Supercomputing Aims and scope Submit manuscript

Abstract

In the design of an interconnection network, one of the most fundamental considerations is the reliability of the network, which can be usually characterized by the fault tolerance of the network. Embedding paths into a network topology is crucial for the network simulation. This paper investigates the problem of embedding spanning disjoint paths in the enhanced hypercube networks with edge fault tolerance. A k-container C(u, v) of a graph G is a set of k-disjoint paths joining u to v. A k-container of G is a \(k^{*}\)-container if it contains all the vertices of G. A bipartite graph H with bipartition \(V_{0}\) and \(V_{1}\) is \(k^{*}\)-laceable if for any \(u\in V_{0}\) and \(v\in V_{1}\) there is a \(k^{*}\)-container between u and v. A bipartite graph H is f-edge fault-tolerant \(k^{*}\)-laceable if \(H-F\) is \(k^{*}\)-laceable for any edge set F of H with \(|F|\le f\). It is shown that the n-dimensional bipartite enhanced hypercube network \(Q_{n,m}\) is f-edge fault-tolerant \(k^{*}\)-laceable for every \(f\le n-1\) and \(f+k\le n+1\). Moreover, the result is optimal with respect to the degree of \(Q_{n,m}\), and some experimental examples are provided to verify the theoretical result.

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

Similar content being viewed by others

Data Availability

Not applicable.

References

  1. Xu JM (2001) Topological Structure and Analysis of Interconnection Networks. Kluwer Academic Publishers, Dordrecht

    MATH  Google Scholar 

  2. Fan JX, Jia XH, Lin XL (2006) Complete path embeddings in crossed cubes. Inf Sci 176(22):3332–3346

    MathSciNet  MATH  Google Scholar 

  3. Fan JX, Jia XH (2008) Edge-pancyclicity and path-embeddability of bijective connection graphs. Inf Sci 178(2):340–351

    MathSciNet  MATH  Google Scholar 

  4. Hsieh SY, Lin TJ, Huang HL (2007) Panconnectivity and edge-pancyclicity of 3-ary N-cubes. J Supercomput 42(2):225–233

    Google Scholar 

  5. Lü HZ (2019) Paired many-to-many two-disjoint path cover of balanced hypercubes with faulty edges. J Supercomput 75(1):400–424

    Google Scholar 

  6. Park JH (2021) A suffcient condition for the unpaired k-disjoint path coverability of interval graphs. J Supercomput 77:6871–6888

    Google Scholar 

  7. Wang SY, Feng K, Zhang SR, Li J (2012) Embedding long cycles in faulty \(k\)-ary \(2\)-cubes. Appl Math Comput 218(9):5409–5413

    MathSciNet  MATH  Google Scholar 

  8. Xu JM, Ma MJ (2009) A survey on cycle and path embedding in some networks. Front Math China 4(2):217–252

    MathSciNet  MATH  Google Scholar 

  9. Wang DJ (2012) Hamiltonian embedding in crossed cubes with failed links. IEEE Trans Parallel Distrib Syst 23(11):2117–2124

    Google Scholar 

  10. Fan WB, Fan JX, Han ZJ, Li P, Zhang YJ, Wang RC (2021) Fault-tolerant hamiltonian cycles and paths embedding into locally exchanged twisted cubes. Front Comput Sci 15(3):153104

    Google Scholar 

  11. Yang YX, Zhang LL (2022) Hamiltonian paths of \(k\)-ary \(n\)-cubes avoiding faulty links and passing through prescribed linear forests. IEEE Trans Parallel Distrib Syst 33(7):1752–1760

    Google Scholar 

  12. Fan JX (2002) Hamilton-connectivity and cycle-embedding of the Möbius cubes. Inf Process Lett 82(2):113–117

    MATH  Google Scholar 

  13. Hao RX, Zhang R, Feng YQ, Zhou JX (2014) Hamiltonian cycle embedding for fault tolerance in balanced hypercubes. Appl Math Comput 244:447–456

    MathSciNet  MATH  Google Scholar 

  14. Hsieh SY, Shiu JY (2007) Cycle embedding of augmented cubes. Appl Math Comput 191(2):314–319

    MathSciNet  MATH  Google Scholar 

  15. Hsieh SY, Wu CD (2009) Optimal fault-tolerant Hamiltonicity of star graphs with conditional edge faults. J Supercomput 49(3):354–372

    Google Scholar 

  16. Hsieh SY, Chen GH, Ho CW (1999) Fault-free Hamiltonian cycles in faulty arrangement graphs. IEEE Trans Parallel Distrib Syst 10(3):223–237

    Google Scholar 

  17. Lü HZ, Zhang HP (2014) Hyper-Hamiltonian laceability of balanced hypercubes. J Supercomput 68(1):302–314

    Google Scholar 

  18. Wang DJ (2001) Embedding hamiltonian cycles into folded hypercubes with faulty links. J Parallel Distrib Comput 61(4):545–564

    MATH  Google Scholar 

  19. Xu M, Hu XD, Xu JM (2007) Edge-pancyclicity and Hamiltonian laceability of the balanced hypercubes. Appl Math Comput 189(2):1393–1401

    MathSciNet  MATH  Google Scholar 

  20. Albert M, Aldred REL, Holton D, Sheehan J (2001) On \(3^{*}\)-connected graphs. Austral J Comb 24:193–208

    MATH  Google Scholar 

  21. Hsu LH, Lin CK (2008) Graph Theory and Interconnection Networks. CRC Press, Boca Raton

    MATH  Google Scholar 

  22. Li J, Liu D, Yuan J (2013) The super spanning connectivity and super spanning laceability of tori with faulty elements. Int J Found Comput Sci 24(6):921–939

    MathSciNet  MATH  Google Scholar 

  23. Teng YH (2016) The spanning connectivity of the arrangement graphs. J Parallel Distrib Comput 98:1–7

    Google Scholar 

  24. Li PS, Xu M (2017) The super spanning connectivity of arrangement graphs. Int J Found Comput Sci 28(8):1047–1072

    MathSciNet  MATH  Google Scholar 

  25. You LT, Fan JX, Han YJ (2018) Super spanning connectivity on WK-recursive networks. Theor Comput Sci 713:42–55

    MathSciNet  MATH  Google Scholar 

  26. Wang JJ, Hsu LH (2018) On the spanning connectivity of the generalized Petersen graphs \(P(n,3)\). Discrete Math 341(3):672–690

    MathSciNet  MATH  Google Scholar 

  27. Huang PY, Hsu LH (2011) The spanning connectivity of line graphs. Appl Math Lett 24(9):1614–1617

    MathSciNet  MATH  Google Scholar 

  28. Lin CK, Huang HM, Hsu LH (2007) On the spanning connectivity of graphs. Discrete Math 307(2):285–289

    MathSciNet  MATH  Google Scholar 

  29. Lin CK, Huang HM, Tan JJM, Hsu LH (2008) On spanning connected graphs. Discrete Math 308(7):1330–1333

    MathSciNet  MATH  Google Scholar 

  30. Sabir E, Vumar E (2014) Spanning connectivity of the power of a graph and Hamilton-connected index of a graph. Graphs Comb 30(6):1551–1563

    MathSciNet  MATH  Google Scholar 

  31. Sabir E, Meng JX (2020) Sufficient conditions for graphs to be spanning connected. Appl Math Comput 378:125198

    MathSciNet  MATH  Google Scholar 

  32. Sabir E, Meng JX (2021) Generalizations of the classics to spanning connectedness. Appl Math Comput 403:126167

    MathSciNet  MATH  Google Scholar 

  33. Simmons G (1978) Almost all n-dimensional rectangular lattices are Hamilton laceable. Congr Numer 21:103–108

    MATH  Google Scholar 

  34. Chang CK, Lin CK, Huang HM, Hsu LH (2004) The super laceability of the hypercubes. Inf Process Lett 92(1):15–21

    MathSciNet  MATH  Google Scholar 

  35. Lin CK, Tan JJM, Hsu DF, Hsu LH (2007) On the spanning connectivity and spanning laceability of hypercube-like networks. Theor Comput Sci 381(1–3):218–229

    MathSciNet  MATH  Google Scholar 

  36. Chang CH, Lin CK, Tan JJM, Huang HM, Hsu LH (2009) The super spanning connectivity and super spanning laceability of the enhanced hypercubes. J Supercomput 48(1):66–87

    Google Scholar 

  37. Lin CK, Huang HM, Hsu LH (2005) The super connectivity of the pancake graphs and the super laceabilityof the star graphs. Theor Comput Sci 339(2–3):257–271

    MATH  Google Scholar 

  38. Cheng BL, Wang DJ, Fan JX (2017) Constructing completely independent spanning trees in crossed cubes. Discrete Appl Math 219:100–109

    MathSciNet  MATH  Google Scholar 

  39. Lin CK, Tan JJM, Hsu DF, Hsu LH (2009) On the spanning fan-connectivity of graphs. Discrete Appl Math 157(7):1342–1348

    MathSciNet  MATH  Google Scholar 

  40. Smys S, Josemin Bala G (2012) Performance analysis of virtual clusters in personal communication networks. Cluster Comput 15(3):211–222

    Google Scholar 

  41. Ma MJ (2010) The spanning connectivity of folded hypercubes. Inf Sci 180(17):3373–3379

    MathSciNet  MATH  Google Scholar 

  42. Lin CK, Teng YH, Tan JJM, Hsu LH, Marušič D (2013) The spanning laceability on the faulty bipartite hypercube-like networks. Appl Math Comput 219:8095–8103

    MathSciNet  MATH  Google Scholar 

  43. Xu M, Naik K, Thulasiraman K (2020) Fault tolerance of hypercube like networks: spanning laceability under edge faults. Theor Comput Sci 835:44–57

    MathSciNet  MATH  Google Scholar 

  44. Leighton FT (1992) Introduction to Parallel Algorithms and Architecture: Arrays, Trees. Morgan Kaufmann, Hypercubes

    MATH  Google Scholar 

  45. Saad Y, Schultz MH (1988) Topological properties of hypercubes. IEEE Trans Comput 37(6):867–872

    Google Scholar 

  46. El-Amawy A, Latifi S (1991) Properties and performance of folded hypercubes. IEEE Trans Parallel Distrib Syst 2(1):31–42

    Google Scholar 

  47. Simó E, Yebra JLA (1997) The vulnerability of the diameter of folded n-cubes. Discrete Math 174(1–3):317–322

    MathSciNet  MATH  Google Scholar 

  48. Tzeng NF, Wei SZ (1991) Enhanced hypercubes. IEEE Trans Comput 40(3):284–294

    Google Scholar 

  49. Liu HM (2009) The structural features of enhanced hypercube networks. ICNC(1):345-348

  50. Ma MJ, West DB, Xu JM (2017) The vulnerability of the diameter of the enhanced hypercubes. Theor Comput Sci 694:60–65

    MathSciNet  MATH  Google Scholar 

  51. Liu M, Liu HM (2013) Paths and cycles embedding on faulty enhanced hypercube networks. Acta Math Sci 33(1):227–246

    MathSciNet  MATH  Google Scholar 

  52. Abraham S, Padmanabhan K (1991) The twisted cube topology for multiprocessors: a study in network asymmetry. J Parallel Distrib Comput 13(1):104–110

    Google Scholar 

  53. Efe K (1992) The crossed cube architecture for parallel computing. IEEE Trans Parallel Distrib Syst 3(5):513–524

    Google Scholar 

  54. Vaidya AS, Rao PSN, Shankar SR (1993) A class of hypercube-like networks. The Fifth IEEE Symposium on Parallel and Distributed Processing, pp 800–803

  55. Park JH, Chwa KY (2004) Hamiltonian properties on the class of hypercube-like networks. Inf Process Lett 91(1):11–17

    MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The authors would like to express their gratitude to the editor and anonymous reviewers for their valuable comments and constructive suggestions on the original manuscript. This research was supported by Natural Science Foundation of Xinjiang, China (No. 2020D04046), Natural Science Foundation of Xinjiang, China (No. 2021D01C116), and National Natural Science Foundation of China (No. 12261085).

Author information

Authors and Affiliations

  1. College of Mathematics and System Sciences, Xinjiang University, Urumqi, 830046, China

    Hongwei Qiao, Jixiang Meng & Eminjan Sabir

Authors
  1. Hongwei Qiao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jixiang Meng
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Eminjan Sabir
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jixiang Meng.

Ethics declarations

Conflict of interest

The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

Additional information

Publisher's Note

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

This work was supported by Natural Science Foundation of Xinjiang, China (No. 2020D04046), Natural Science Foundation of Xinjiang, China (No. 2021D01C116), and National Natural Science Foundation of China (No. 12261085).

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

Qiao, H., Meng, J. & Sabir, E. The edge fault-tolerant spanning laceability of the enhanced hypercube networks. J Supercomput 79, 6070–6086 (2023). https://doi.org/10.1007/s11227-022-04896-4

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11227-022-04896-4

Keywords