Skip to main content
SpringerLink
Log in

Survey on path and cycle embedding in some networks

  • Survey Article
  • Published:
Frontiers of Mathematics in China Aims and scope Submit manuscript

Abstract

To find a cycle (resp. path) of a given length in a graph is the cycle (resp. path) embedding problem. To find cycles of all lengths from its girth to its order in a graph is the pancyclic problem. A stronger concept than the pancylicity is the panconnectivity. A graph of order n is said to be panconnected if for any pair of different vertices x and y with distance d there exist xy-paths of every length from d to n. The pancyclicity or the panconnectivity is an important property to determine if the topology of a network is suitable for some applications where mapping cycles or paths of any length into the topology of the network is required. The pancyclicity and the panconnectivity of interconnection networks have attracted much research interest in recent years. A large amount of related work appeared in the literature, with some repetitions. The purpose of this paper is to give a survey of the results related to these topics for the hypercube and some hypercube-like networks.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Akers S B, Harel D, Krishnamurthy B. The star graph, An attractive alternative to the n-cube. In: Sahni S, ed. Proceedings of the 1987 International Conference on Parallel Processing, August 17–21, 1987. University Park: Pennsylvania State Univ Press, 1987, 393–400

    Google Scholar 

  2. Akers S B, Krishnamurthy B. A group-theoretic model for symmetric interconnection networks. In: Proceedings of the 1986 International Conference on Parallel Processing. 1986, 216–223

  3. Akers S B, Krisnamurthy B. A group theoretic model for symmetric interconnection networks. IEEE Transactions on Computers, 1989, 38(4): 555–566

    MATH  Google Scholar 

  4. Akl S G. Parallel Computation: Models and Methods. Upper Saddle River: Prentice-Hall, 1997

    Google Scholar 

  5. Alavi Y, Williamson J E. Panconnected graphs. Studia Scientiarum Mathematicarum Hungarica, 1975, 10(1–2): 19–22

    MathSciNet  Google Scholar 

  6. Alspach B, Bermond J C, Sotteau D. Decomposition into cycles I. Hamiltonian decomposition. Technical Report 87-12. Simon Fraser University, 1987

  7. Alspach B, Hare D. Edge-pancyclic block-intersection graphs. Discrete Mathematics, 1991, 97(1-3): 17–24

    MATH  MathSciNet  Google Scholar 

  8. Araki T, Kikuchi Y. Hamiltonian laceability of bubble-sort graphs with edge faults. Information Sciences, 2007, 177(13): 2679–2691

    MATH  MathSciNet  Google Scholar 

  9. Araki T, Shibata Y. Pancyclicity of recursive circulant graphs. Information Processing Letters, 2002, 81: 187–190

    MATH  MathSciNet  Google Scholar 

  10. Ashir Y A, Stewart T A. On embedding cycles in k-ary n-cubes. Parallel Processing Letters, 1997, 7(1): 49–55

    MathSciNet  Google Scholar 

  11. Ashir Y A, Stewart I A. Fault-tolerant embedding of Hamiltonian circuits in k-ary n-cube. SIAM Journal on Discrete Mathematics, 2002, 15(3): 317–328

    MATH  MathSciNet  Google Scholar 

  12. Bettayeb S. On the k-ary Hypercube. Theoretical Computer Science, 1995, 140: 333–339

    MATH  MathSciNet  Google Scholar 

  13. Bondy J A. Pancyclic graphs. I. Journal of Combinatorial Theory, 1971, 11: 80–84

    MATH  MathSciNet  Google Scholar 

  14. Bose B, Broeg B, Kwon Y, Ashir Y. Lee distance and topological properties of k-ary n-cubes. IEEE Transactions on Computers, 1995, 44: 1021–1030

    MATH  MathSciNet  Google Scholar 

  15. Chan M Y, Lee S J. On the existence of Hamiltonian circuits in faulty hypercubes. SIAM Journal on Discrete Mathematics, 1991, 4: 511–527

    MATH  MathSciNet  Google Scholar 

  16. Chan M Y, Lee S J. Distributed fault-tolerant embedding of rings in hypercubes. Journal of Parallel and Distributed Computing, 1991, 11: 63–71

    Google Scholar 

  17. Chang C-H, Lin C-K, Huang H-M, Hsu L-H. The super laceability of the hypercubes. Information Processing Letters, 2004, 92(1): 15–21

    MathSciNet  MATH  Google Scholar 

  18. Chang C-P, Sung T-Y, Hsu L-H. A new shortest path routing algorithm and embedding cycles of crossed cube. Parallel Architectures, Algorithms, and Networks, 1997. (I-SPAN’97) Proceedings. Third International Symposium on 18-20 Dec 1997. 125–131

  19. Chang C-P, Wang J-N, Hsu L-H. Topological properties of twisted cube. Information Science, 1999, 113: 147–167

    MATH  MathSciNet  Google Scholar 

  20. Chang J-M, Yang J-S, Wang Y-L, Cheng Y. Panconnectivity, fault-tolerant hamiltonicity and hamiltonian-connectivity in alternating group graphs. Networks, 2004, 44(4): 302–310

    MATH  MathSciNet  Google Scholar 

  21. Chang J-M, Yang J-S. Fault-tolerant cycle embedding in alternating group graphs. Applied Mathematics and Computation, 2008, 197(2): 760–767

    MATH  MathSciNet  Google Scholar 

  22. Chang Q-Y, Ma M-J, Xu J-M. Fault-tolerant pancyclicity of locally twisted cubes. Journal of University of Science and Technology of China, 2006, 36(6): 607–610, 673 (in Chinese)

    MathSciNet  Google Scholar 

  23. Chang Q-Y, Ma M-J, Xu J-M. Fault-tolerant pancyclicity of twisted cubes. Operation Research and Management Science, 2007, 16(1): 52–57 (in Chinese)

    Google Scholar 

  24. Chen G H, Fu J S, Fang J F. Hypercomplete: a pancylic recursive topology for large-scale distributed multicomputer systems. Networks, 2000, 35(1): 56–69

    MATH  MathSciNet  Google Scholar 

  25. Chen G H, Hwang S C. Cycle in butterfly graphs. Networks, 2000, 35(2): 161–171

    MATH  MathSciNet  Google Scholar 

  26. Chen M Y, Shin K G. Processor allocation in an n-cube multiprocessor using gray codes. IEEE Transactions on Computers, 1987, 36: 1396–1407

    Article  Google Scholar 

  27. Chen X-B. Cycles passing through prescribed edges in a hypercube with some faulty edges. Information Processing Letters, 2007, 104(6): 211–215

    MathSciNet  Google Scholar 

  28. Chen X-B. Some results on topological properties of folded hypercubes. Information Processing Letters, DOI: 10.1016/j.ipl.2008.12.005

  29. Chen Y-C, Tsai C-H, Hsu L-H, Tan J J M. On some super fault-tolerant Hamiltonian graphs. Applied Mathematics and Computation, 2004, 148: 729–741

    MATH  MathSciNet  Google Scholar 

  30. Chen Y-Y, Duh D-R, Ye T-L, Fu J-S. Weak-vertex-pancyclicity of (n, k)-star graphs. Theoretical Computer Science, 2008, 396(3): 191–199

    MATH  MathSciNet  Google Scholar 

  31. Cheng E, Lipman M. Fault tolerant routing in split-stars and alternating group graphs. Congressus Numerantium, 1999, 139: 21–32

    MATH  MathSciNet  Google Scholar 

  32. Cheng E, Lipman M-J. Vulnerability issues of star graphs, alternating group graphs and split-stars: strength and toughness. Discrete Applied Mathematics, 2002, 118(3): 163–179

    MATH  MathSciNet  Google Scholar 

  33. Cheng E, Lipman M-J, Park H. Super connectivity of star graphs, alternating group graphs and split-stars. Ars Combinatoria, 2001, 59: 107–116

    MATH  MathSciNet  Google Scholar 

  34. Chiang W K, Chen R J. The (n, k)-star graphs: A generalized star graph. Information Processing Letters, 1995, 56: 259–264

    MATH  MathSciNet  Google Scholar 

  35. Chiang W K, Chen R J. On the arrangement graph. Information Processing Letters, 1998, 66: 215–219

    MATH  MathSciNet  Google Scholar 

  36. Choudum S A, Sunitha V. Wide-diameter of augmented cubes. Technical Report. Department of Mathematics, Indian Institute of Technology Madras, Chennai, November 2000

    Google Scholar 

  37. Choudum S A, Sunitha V. Automorphisms of augmented cubes. Technical Report. Department of Mathematics, Indian Institute of Technology Madras, Chennai, March 2001

    Google Scholar 

  38. Choudum S A, Sunitha V. Augmented cubes. Networks, 2002, 40(2): 71–84

    MATH  MathSciNet  Google Scholar 

  39. Cull P, Larson S M. The Möbius cubes. IEEE Transactions on Computers, 1995, 44(5): 647–659

    MATH  MathSciNet  Google Scholar 

  40. Cull P, Larson S M. On generalized twisted cubes. Information Processing Letters, 1995, 55: 53–55

    MATH  Google Scholar 

  41. Day K, Tripathi A. Arrangement graphs: A class of generalized star graphs. Information Processing Letters, 1992, 42(5): 235–241

    MATH  MathSciNet  Google Scholar 

  42. Day K, Tripathi A. Embedding of cycles in arrangement graphs. IEEE Transactions on Computers, 1993, 42(8): 1002–1006

    MathSciNet  Google Scholar 

  43. Du Z-Z, Jing J, Ma M-J, Xu J-M. Cycle embedding in hypercubes with faulty vertices and edges. Journal of University of Science and Technology of China, 2008, 38(9): 1020–1023

    MathSciNet  Google Scholar 

  44. Efe K. A variation on the hypercube with lower diameter. IEEE Transactions on Computers, 1991, 40(11): 1312–1316

    Google Scholar 

  45. El-Amawy A, Latifi S. Properties and performance of folded hypercubes. IEEE Transactions on Parallel and Distributed Systems, 1991, 2(3): 31–42

    Google Scholar 

  46. Esfahanian A H. Generalized measures of fault tolerance with application to n-cube networks. IEEE Transactions on Computers, 1989, 38(11): 1586–1591

    Google Scholar 

  47. Fan J. Hamilton-connectivity and cycle-embedding of the Möbius cubes. Information Processing Letters, 2002, 82: 113–117

    MATH  MathSciNet  Google Scholar 

  48. Fan J, Jia X, Lin X. Complete path embeddings in crossed cubes. Information Sciences, 2006, 176(22): 3332–3346

    MATH  MathSciNet  Google Scholar 

  49. Fan J, Lin X, Jia X. Node-pancyclicity and edge-pancyclicity of crossed cubes. Information Processing Letters, 2005, 93(3): 133–138

    MathSciNet  MATH  Google Scholar 

  50. Fan J, Lin X, Jia X. Optimal path embedding in crossed cubes. IEEE Transactions on Parallel and Distributed Systems, 2005, 16(12): 1190–1200

    Google Scholar 

  51. Fan J, Lin X, Jia X. Optimal fault-tolerant embedding of paths in twisted cubes. Journal of Parallel and Distributed Computing, 2007, 67(2): 205–214

    MATH  Google Scholar 

  52. Fan J, Lin X, Jia X, Lau R W H. Edge-pancyclicity of twisted cubes. Lecture Notes in Computer Science, 2005, 3827: 1090–1099

    MathSciNet  Google Scholar 

  53. Fu J-S. Fault-tolerant cycle embedding in the hypercube. Parallel Computing, 2003, 29: 821–832

    MathSciNet  Google Scholar 

  54. Fu J-S. Longest fault-free paths in hypercubes with vertex faults. Information Sciences, 2006, 176: 759–771

    MATH  MathSciNet  Google Scholar 

  55. Fu J-S. Conditional fault-tolerant hamiltonicity of star graphs. Parallel Computing, 2007, 33: 488–496

    MathSciNet  Google Scholar 

  56. Fu J-S. Fault-free cycles in folded hypercubes with more faulty elements. Information Processing Letters, 2008, 108(5): 261–263

    MathSciNet  Google Scholar 

  57. Fu J-S. Fault-free hamiltonian cycles in twisted cubes with conditional link faults. Theoretical Computer Science, 2008, 407(1–3): 318–329

    MATH  MathSciNet  Google Scholar 

  58. Germa A, Heydemann M C, Sotteau D. Cycles in the cube-connected cycles graphs. Discrete Applied Mathematics, 1998, 83: 135–155

    MATH  MathSciNet  Google Scholar 

  59. Harary F, Hayes J P, Wu H J. A survey of the theory of hypercube graphs. Computers and Mathematics with Applications, 1988, 15(4): 277–289

    MATH  MathSciNet  Google Scholar 

  60. Harary F, Lewinter M. Hypercubes and other recursively defined Hamilton laceable graphs. Congressus Numerantium, 1987, 60: 81–84

    MathSciNet  Google Scholar 

  61. Heydari M H, Sudborough I H. On the diameter of the pancake network. Journal of Algorithms, 1997, 25: 67–94

    MATH  MathSciNet  Google Scholar 

  62. Hilbers P A J, Koopman M R J, van de Snepscheut J L A. The twisted cubes. Lecture Notes in Computer Science, 1987, 258–259: 152–159

    Google Scholar 

  63. Hobbs A. The square of a block is vertex pancyclic. Journal of Combinatorical Theory, B, 1976, 20(1): 1–4

    MATH  MathSciNet  Google Scholar 

  64. Hsieh S-Y. Embedding longest fault-free paths onto star graphs with more vertex faults. Theoretical Computer Science, 2005, 337(1–3): 370–378

    MATH  MathSciNet  Google Scholar 

  65. Hsieh S-Y. Fault-tolerant cycle embedding in the hypercube with more both faulty vertices and faulty edges. Parallel Computing, 2006, 32(1): 84–91

    MathSciNet  Google Scholar 

  66. Hsieh S-Y. Some edge-fault-tolerant properties of the folded hypercube. Networks, 2008, 52(2): 92–101

    MathSciNet  Google Scholar 

  67. Hsieh S-Y. A note on cycle embedding in folded hypercubes with faulty elements. Information Processing Letters, 2008, 108(2): 81

    MathSciNet  Google Scholar 

  68. Hsieh S-Y, Chang N-W. Hamiltonian path embedding and pancyclicity on the Möbius cube with faulty nodes and faulty edges. IEEE Transactions on Computers, 2006, 55(7): 854–863

    Google Scholar 

  69. Hsieh S-Y, Chen C-H. Pancyclicity on Möbius cubes with maximal edge faults. Parallel Computing, 2004, 30(3): 407–421

    MathSciNet  Google Scholar 

  70. Hsieh S-Y, Chen G-H, Ho C-W. Fault-free hamiltonian cycles in faulty arrangement graphs. IEEE Trans Parallel and Distributed Systems, 1999, 10(3): 223–237

    Google Scholar 

  71. Hsieh S-Y, Chen G-H, Ho C-W. Hamiltonian-laceability of star graphs. Networks, 2000, 36(4): 225–232

    MATH  MathSciNet  Google Scholar 

  72. Hsieh S-Y, Chen G-H, Ho C-W. Longest fault-free paths in star graphs with vertex faults. Theoretical Computer Science, 2001, 262: 215–227

    MATH  MathSciNet  Google Scholar 

  73. Hsieh S-Y, Chen G-H, Ho C-W. Longest fault-free paths in star graphs with edge faults. IEEE Transactions on Computers, 2001, 50(9): 960–971

    Google Scholar 

  74. Hsieh S-Y, Kuo C-N. 1-vertex-Hamiltonian-laceability of hypercubes with maximal edge faults. Journal of Interconnection Networks, 2005, 6(4): 407–415

    Google Scholar 

  75. Hsieh S-Y, Kuo C-N. Hamilton-connectivity and strongly Hamiltonian-laceability of folded hypercubes. Computers and Mathematics with Applications, 2007, 53(7): 1040–1044

    MATH  MathSciNet  Google Scholar 

  76. Hsieh S-Y, Lee C-W. Conditional edge-fault hamiltonicity of matching composition networks. IEEE Transactions on Parallel and Distributed Systems, DOI: 10.1109/TPDS.2008.123

  77. Hsieh S-Y, Lin T J. Embedding cycles and paths in a k-ary n-cube. In: Proceedings of the 13th International Conference on Parallel and Distributed Systems (ICPADS). IEEE Computer Society, 2007, 1–7

  78. Hsieh S-Y, Lin T-J. Panconnectivity and edge-pancyclicity of k-ary n-cubes. Networks, DOI: 10.1002/net.20290

  79. Hsieh S-Y, Lin T J, Huang H L. Panconnectivity and edge-pancyclicity of 3-ary n-cubes. Journal of Supercomputing, 2007, 42: 225–233

    Google Scholar 

  80. Hsieh S-Y, Shen T-H. Edge-bipancyclicity of a hypercube with faulty vertices and edges. Discrete Applied Mathematics, 2008, 156(10): 1802–1808

    MATH  MathSciNet  Google Scholar 

  81. Hsieh S-Y, Shiu J-Y. Cycle embedding of augmented cubes. Applied Mathematics and Computation, 2007, 191: 314–319

    MathSciNet  Google Scholar 

  82. Hsieh S-Y, Wu C-D. Optimal fault-tolerant hamiltonicity of star graphs with conditional edge faults. Journal of Supercomputing, DOI: 10.1007/s11227-008-0242-9

  83. Hsu H-C, Chiang L-C, Tan J J M, Hsu L-H. Fault hamiltonicity of augmented cubes. Parallel Computing, 2005, 31(1): 131–145

    MathSciNet  Google Scholar 

  84. Hsu H-C, Hsieh Y-L, Tan J J M, Hsu L-H. Fault hamiltonicity and fault hamiltonian connectivity of the (n, k)-star graphs. Networks, 2003, 42(4): 189–201

    MATH  MathSciNet  Google Scholar 

  85. Hsu H-C, Li T-K, Tan J J M, Hsu L-H. Fault hamiltonicity and fault hamiltonian connectivity of the arrangement graphs. IEEE Transactions on Computers, 2004, 53(1): 39–52

    MathSciNet  Google Scholar 

  86. Hu K-S, Yeoh S-S, Chen C-Y, Hsu L-H. Node-pancyclicity and edge-pancyclicity of hypercube variants. Information Processing Letters, 2007, 102(1): 1–7

    MathSciNet  Google Scholar 

  87. Huang J, Xu J-M. Multiply-twisted hypercube with four or less dimensions is vertex-transitive. Chinese Quarterly Journal of Mathematics, 2005, 20(4): 430–434

    MathSciNet  Google Scholar 

  88. Huang K, Wu J. Area efficient layout of balanced hypercubes. Int’1 J High Speed Electronics and Systems, 1995, 6(4): 631–646

    Google Scholar 

  89. Huang S-C, Chen C-H. Cycles in butterfly graphs. Networks, 2000, 35: 1–11

    MathSciNet  Google Scholar 

  90. Huang W-T, Chen W-K, Chen C-H. Pancyclicity of Möbius cubes. In: Proceedings of the Ninth international Conference on Parallel and Distributed Systems (ICPADS’02) on 17–20 Dec 2002. 591–596

  91. Huang W T, Chuang Y C, Tan J J M, Hsu L H. Fault-free Hamiltonian cycle in faulty Möbius cubes. Computación y Systemas, 2000, 4(2): 106–114

    Google Scholar 

  92. Huang W T, Chuang Y C, Tan J J M, Hsu L H. On the fault-tolerant hamiltonicity of faulty crosses cubes. IEICE Trans on Fundamentals, 2002, E85-A(6): 1359–1370

    Google Scholar 

  93. Huang W T, Tan J J M, Huang C N, Hsu L H. Fault-tolerant hamiltonicity of twisted cubes. J Parallel and Distributed Computing, 2002, 62: 591–604

    MATH  Google Scholar 

  94. Hung C-N, Hsu H-C, Liang K-Y, Hsu L-H. Ring embedding in faulty pancake graphs. Information Processing Letters, 2003, 86: 271–275

    MATH  MathSciNet  Google Scholar 

  95. Hung H-S, Fu J-S, Chen G-H. Fault-free Hamiltonian cycles in crossed cubes with conditional link faults. Information Sciences, 2007, 177(24): 5664–5674

    MATH  MathSciNet  Google Scholar 

  96. Jing J, Du Z-Z, Ma M-J, Xu J-M. Edge-fault-tolerant bipanconnectivity of hypercubes. Journal of University of Science and Technology of China, 2008, 38(9): 1017–1019

    MathSciNet  Google Scholar 

  97. Jwo J S, Lakshmivarahan S, Dhall S K. Embedding of cycles and grids in star graphs. J Circuits Syst Computers, 1991, 1: 43–74

    Google Scholar 

  98. Jwo J S, Lakshmivarahan S, Dhall S K. A new class of interconnection networks based on the alternating group. Networks, 1993, 33: 315–326

    MathSciNet  Google Scholar 

  99. Kanevsky A, Feng C. On the embedding of cycles in pancake graphs. Parallel Computing, 1995, 21: 923–936

    MATH  MathSciNet  Google Scholar 

  100. Kikuchi Y, Araki T. Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs. Information Processing Letters, 2006, 100(2): 52–59

    MathSciNet  Google Scholar 

  101. Kim H-C, Park J-H. Fault hamiltonicity of two-dimensional torus networks. In: Proceedings of the Workshop on Algorithms and Computation WAAC’00, Tokyo, Japan. 2000, 110–117

  102. Kueng T-L, Liang T, Hsu L-H, Tan J J M. Long paths in hypercubes with conditional node-faults. Information Sciences, 2009, 179(5): 667–681

    MATH  MathSciNet  Google Scholar 

  103. Kulasinghe P, Bettayeb S. Multiply-twisted hypercube with five of more dimensions is not vertex-transitive. Information Processing Letters, 1995, 53: 33–36

    MATH  MathSciNet  Google Scholar 

  104. Latifi S, Zheng S, Bagherzadeh N. Optimal ring embedding in hypercubes with faulty links. In: Proc Fault-Tolerant Computing Symp. 1992, 178–184

  105. Leighton F T. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. San Mateo: Morgan Kaufman, 1992

    MATH  Google Scholar 

  106. Lewinter M, Widulski W. Hyper-Hamilton laceable and caterpillar-spannable product graphs. Computers and Mathematics with Applications, 1997, 34(1): 99–104

    MATH  MathSciNet  Google Scholar 

  107. Leu Y-R, Kuo S Y. Distributed fault-tolerant ring embedding and reconfiguration in hypercubes. IEEE Transactions on Computers, 1999, 48(1): 81–88

    MathSciNet  Google Scholar 

  108. Li T-K. Cycle embedding in star graphs with edge faults. Applied Mathematics and Computation, 2005, 167(2): 891–900

    MATH  MathSciNet  Google Scholar 

  109. Li T-K, Tan J J M, Hsu L-H. Hyper hamiltonian laceability on edge fault star graph. Information Sciences, 2004, 165(1–2): 59–71

    MATH  MathSciNet  Google Scholar 

  110. Li T K, Tsai C H, Tan J J M, Hsu L H. Bipannectivity and edge-fault-tolerant bipancyclicity of hypercubes. Information Processing Letters, 2003, 87(2): 107–110

    MathSciNet  MATH  Google Scholar 

  111. Lin C-K, Huang H-M, Hsu L-H. The super connectivity of the pancake graphs and the super laceability of the star graphs. Theoretical Computer Science, 2005, 339(2–3): 257–271

    MATH  MathSciNet  Google Scholar 

  112. Lo R S, Chen G H. Embedding hamiltonian path in faulty arrangement graphs with the backtracking method. IEEE Trans Parallel and Distributed Systems, 2001, 12(2): 209–222

    MathSciNet  Google Scholar 

  113. Ma M-J, Liu G-Z, Pan X-F. Path embedding in faulty hypercubes. Applied Mathematics and Computation, 2007, 192(1): 233–238

    MathSciNet  Google Scholar 

  114. Ma M-J, Liu G-Z, Xu J-M. Panconnectivity and edge-fault-tolerant pancyclicity of augmented cubes. Parallel Computing, 2007, 33(1): 36–42

    MathSciNet  Google Scholar 

  115. Ma M-J, Liu G-Z, Xu J-M. Fault-tolerant embedding of paths in crossed cubes. Theoretical Computer Science, 2008, 407(1–3): 110–116

    MATH  MathSciNet  Google Scholar 

  116. Ma M-J, Xu J-M. Edge-pancyclicity of crossed cubes. Journal of University of Science and Technology of China, 2005, 35(3): 329–333

    MATH  MathSciNet  Google Scholar 

  117. Ma M-J, Xu J-M. Panconnectivity of locally twisted cubes. Applied Mathematics Letters, 2006, 19(7): 681–685

    MathSciNet  Google Scholar 

  118. Ma M-J, Xu J-M. Weak edge-pancyclicity of locally twisted cubes. Ars Combinatoria, 2008, 89: 89–94

    MathSciNet  Google Scholar 

  119. Ma M-J, Xu J-M. Transitivity and panconnectivity of folded hypercubes. Ars Combinatoria (to appear)

  120. Ma M-J, Xu J-M, Du Z-Z. Edge-fault-tolerant hamiltonicity of folded hypercubes. Journal of University of Science and Technology of China, 2006, 36(3): 244–248

    Google Scholar 

  121. Mitchem J, Schmeichel E. Pancyclic and bipancyclic graphs—a survey. In: Proc First Colorado Symp on Graphs and Applications, Boulder, CO, 1982. New York: Wiley-Interscience, 1985, 271–278

    Google Scholar 

  122. Ore O. Hamilton connected graphs. Journal de Mathématiques Pures et Appliquées, 1963, 42(9): 21–27

    MATH  MathSciNet  Google Scholar 

  123. Park C D, Chwa K Y. Hamiltonian properties on the class of hypercube-like networks. Information Processing Letters, 2004, 91(1): 11–17

    MathSciNet  MATH  Google Scholar 

  124. Park J-H, Chwa K-Y. Recursive circulants and their embeddings among hypercubes. Theoretical Computer Science, 2000, 244: 35–62

    MATH  MathSciNet  Google Scholar 

  125. Park J H, Kim H C, Lim H S. Panconnectivity and pancyclicity of hypercube-like interconnection networks with fault elements. Theoretical Computer Science, 2007, 377(1–3): 170–180

    MATH  MathSciNet  Google Scholar 

  126. Provost F J, Melhem R. Distributed fault tolerant embedding of binary tree and rings in hypercubes. In: Proc Internat Workshop on Defect and Fault Tolerance in VLSI Systems. 1988, 831–838

  127. Saad Y, Schultz M H. Topological properties of hypercubes. IEEE Transactions on Computers, 1988, 37(7): 867–872

    Google Scholar 

  128. Sen A, Sengupta A, Bandyopadhyay S. On some topological properties of hypercube, incomplete hypercube and supercube. In: Proceedings of the International Parallel Processing Symposium, Newport Beach, April, 1993. 636–642

  129. Sengupta A. On ring in hypercubes with faulty nodes and links. Information Processing Letters, 1998, 68: 207–214

    MathSciNet  Google Scholar 

  130. Shih L-M, Tan J J M, Hsu L-H. Edge-bipancyclicity of conditional faulty hypercubes. Information Processing Letters, 2007, 105(1): 20–25

    MathSciNet  Google Scholar 

  131. Simmons G. Almost all n-dimensional rectangular lattices are Hamilton laceable. Congressus Numerantium, 1978, 21: 103–108

    MathSciNet  Google Scholar 

  132. Stewart I A, Xiang Y. Bipanconnectivity and bipancyclicity in k-ary n-cubes. IEEE Transactions on Parallel and Distributed Systems, 2009, 20(1): 25–33

    Google Scholar 

  133. Sun C-M, Hung C-N, Huang H-M, Hsu L-H, Jou Y-D. Hamiltonian laceability of faulty hypercubes. Journal of Interconnection Networks, 2007, 8(2): 133–145

    Google Scholar 

  134. Tchuente M. Generation of permutations by graphical exchanges. Ars Combinatoria, 1982, 14: 115–122

    MATH  MathSciNet  Google Scholar 

  135. Teng Y-H, Tan J J M, Hsu L-H. Panpositionable hamiltonicity and panconnectivity of the arrangement graphs. Applied Mathematics and Computation, 2008, 198(1): 414–432

    MATH  MathSciNet  Google Scholar 

  136. Tsai C H. Linear array and ring embeddings in conditional faulty hypercubes. Theoretical Computer Science, 2004, 314(3): 431–443

    MATH  MathSciNet  Google Scholar 

  137. Tsai C-H. Embedding various even cycles in the hypercube with mixed link and node failures. Applied Mathematics Letters, 2008, 21(8): 855–860

    MATH  MathSciNet  Google Scholar 

  138. Tsai C-H, Jiang S-Y. Path bipancyclicity of hypercubes. Information Processing Letters, 2007, 101(3): 93–97

    MathSciNet  Google Scholar 

  139. Tsai C-H, Lai Y-C. Conditional edge-fault-tolerant edge-bipancyclicity of hypercubes. Information Sciences, 2007, 177(24): 5590–5597

    MATH  MathSciNet  Google Scholar 

  140. Tsai C H, Liang T, Hsu L-H, Lin M-Y. Cycle embedding a faulty wrapped butterfly graphs. Networks, 2003, 42(2): 85–96

    MATH  MathSciNet  Google Scholar 

  141. Tsai C-H, Tan J-M, Liang T, Hsu L-H. Fault-tolerant Hamiltonian laceability of hypercubes. Information Processing Letters, 2002, 83(6): 301–306

    MATH  MathSciNet  Google Scholar 

  142. Tsai P-Y, Chen G-H, Fu J-S. Edge-fault-tolerant pancyclicity of alternating group graphs. Networks, DOI: 10.1002/net.20291

  143. Tsai P-Y, Fu J-S, Chen G-H. Edge-fault-tolerant Hamiltonicity of pancake graphs under the conditional fault model. Theoretical Computer Science, 2008, 409(3): 450–460

    MATH  MathSciNet  Google Scholar 

  144. Tsai P-Y, Fu J-S, Chen G-H. Fault-free longest paths in star networks with conditional link faults. Theoretical Computer Science, 2009, 410(8–10): 766–775

    MATH  MathSciNet  Google Scholar 

  145. Tseng Y-C. Embedding a ring in a hypercube with both faulty links and faulty nodes. Information Processing Letters, 1996, 59: 217–222

    MATH  MathSciNet  Google Scholar 

  146. Tseng Y C, Chang S H, Sheu J P. Fault-tolerant ring embedding in a star graph with both link and node failures. IEEE Trans Parallel and Distributed Systems, 1997, 8(12): 1185–1195

    Google Scholar 

  147. Wang D, An T, Pan M, Wang K, Qu S. Hamiltonianlike properties of k-ary n-cubes. In: Proceedings of Sixth International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT05), 2005. 1002–1007

  148. Wang D-J. Embedding hamiltonian cycles into folded hypercubes with faulty links. Journal of Parallel and Distributed Computing, 2001, 61: 545–564

    MATH  Google Scholar 

  149. Wang H-L, Wang J-W, Xu J-M. Edge-fault-tolerant bipanconnectivity of hypercubes. Information Science, 2009, 179(4): 404–409

    MATH  Google Scholar 

  150. Wang W-W, Ma M-J, Xu J-M. Fault-tolerant pancyclicity of augmented cubes. Information Processing Letters, 2007, 103(2): 52–56

    MathSciNet  Google Scholar 

  151. Williamson J E. Panconnected graphs II. Periodica Mathematica Hungarica, 1977, 8(2): 105–116

    MATH  MathSciNet  Google Scholar 

  152. Wu J, Huang K. The balanced hypercubes: A cube-based system for fault-tolerant applications. IEEE Transactions on Computers, 1997, 46(4): 484–490

    MathSciNet  Google Scholar 

  153. Xu J-M. Topological Structure and Analysis of Interconnection Networks. Dordrecht/Boston/London: Kluwer Academic Publishers, 2001

    MATH  Google Scholar 

  154. Xu J-M, Du Z-Z, Xu M. Edge-fault-tolerant edge-bipancyclicity of hypercubes. Information Processing Letters, 2005, 96(4): 146–150

    MathSciNet  Google Scholar 

  155. Xu J-M, Ma M-J. Cycles in folded hypercubes. Applied Mathematics Letters, 2006, 19(2): 140–145

    MATH  MathSciNet  Google Scholar 

  156. Xu J-M, Ma M-J, Lu M. Paths in Möbius cubes and crossed cubes. Information Processing Letters, 2006, 97(3): 94–97

    MathSciNet  Google Scholar 

  157. Xu J-M, Ma M-J, Du Z-Z. Edge-fault-tolerant properties of hypercubes and folded hypercubes. Australasian Journal of Combinatorics, 2006, 35: 7–16

    MATH  MathSciNet  Google Scholar 

  158. Xu M, Hu X-D, Xu J-M. Edge-pancyclicity and hamiltonian laceability of balanced hypercubes. Applied Mathematics and Computation, 2007, 189(2): 1393–1401

    MATH  MathSciNet  Google Scholar 

  159. Xu M, Hu X-D, Zhu Q. Edge-bipancyclicity of star graphs under edge-fault tolerant. Applied Mathematics and Computation, 2006, 183(2): 972–979

    MATH  MathSciNet  Google Scholar 

  160. Xu M, Xu J-M. Edge-pancyclicity of Möbius cubes. Information Processing Letters, 2005, 96(4): 136–140

    MathSciNet  Google Scholar 

  161. Yang M-C, Li T-K, Tan J J M, Hsu L-H. Fault-tolerant cycle-embedding of crossed cubes. Information Processing Letters, 2003, 88(4): 149–154

    MathSciNet  MATH  Google Scholar 

  162. Yang M-C, Li T-K, Tan J J M, Hsu L-H. On embedding cycles into faulty twisted cubes. Information Sciences, 2006, 176(6): 676–690

    MATH  MathSciNet  Google Scholar 

  163. Yang M-C, Tan J J M, Hsu L-H. Hamiltonian circuit and linear array embeddings in faulty k-ary n-cubes. Journal of Parallel and Distributed Computing, 2007, 67(4): 362–368

    MATH  Google Scholar 

  164. Yang P J, Tien S B, Raghavendra C S. Embedding of rings and meshes onto faulty hypercubes using free dimensions. IEEE Transactions on Computers, 1994, 43(5): 608–613

    Google Scholar 

  165. Yang X F, Evans D J, Megson G M. The locally twisted cubes. International Journal of Computer Mathematics, 2005, 82(4): 401–413

    MathSciNet  Google Scholar 

  166. Yang X F, Evans D J, Megson G M, Tang Y Y. On the path-connectivity, vertexpancyclicity, and edge-pancyclicity of crossed cubes. Neural, Parallel and Scientific Computations, 2005, 13(1): 107–118

    MATH  MathSciNet  Google Scholar 

  167. Yang X F, Megson G M, Evans D J. Locally twisted cubes are 4-pancyclic. Applied Mathematics Letters, 2004, 17: 919–925

    MATH  MathSciNet  Google Scholar 

  168. Yang X F, Megson G M, Evans D J. Pancyclicity of Möbius cubes with faulty nodes. Microprocessors and Microsystems, 2006, 30(3): 165–172

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Science and Technology of China, Hefei, 230026, China

    Jun-Ming Xu

  2. Department of Mathematics, Zhejiang Normal University, Jinhua, 321004, China

    Meijie Ma

Authors
  1. Jun-Ming Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Meijie Ma
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jun-Ming Xu.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Xu, JM., Ma, M. Survey on path and cycle embedding in some networks. Front. Math. China 4, 217–252 (2009). https://doi.org/10.1007/s11464-009-0017-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11464-009-0017-5

Keywords

MSC

Search

Navigation