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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
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
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
Akers S B, Krisnamurthy B. A group theoretic model for symmetric interconnection networks. IEEE Transactions on Computers, 1989, 38(4): 555–566
Akl S G. Parallel Computation: Models and Methods. Upper Saddle River: Prentice-Hall, 1997
Alavi Y, Williamson J E. Panconnected graphs. Studia Scientiarum Mathematicarum Hungarica, 1975, 10(1–2): 19–22
Alspach B, Bermond J C, Sotteau D. Decomposition into cycles I. Hamiltonian decomposition. Technical Report 87-12. Simon Fraser University, 1987
Alspach B, Hare D. Edge-pancyclic block-intersection graphs. Discrete Mathematics, 1991, 97(1-3): 17–24
Araki T, Kikuchi Y. Hamiltonian laceability of bubble-sort graphs with edge faults. Information Sciences, 2007, 177(13): 2679–2691
Araki T, Shibata Y. Pancyclicity of recursive circulant graphs. Information Processing Letters, 2002, 81: 187–190
Ashir Y A, Stewart T A. On embedding cycles in k-ary n-cubes. Parallel Processing Letters, 1997, 7(1): 49–55
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
Bettayeb S. On the k-ary Hypercube. Theoretical Computer Science, 1995, 140: 333–339
Bondy J A. Pancyclic graphs. I. Journal of Combinatorial Theory, 1971, 11: 80–84
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
Chan M Y, Lee S J. On the existence of Hamiltonian circuits in faulty hypercubes. SIAM Journal on Discrete Mathematics, 1991, 4: 511–527
Chan M Y, Lee S J. Distributed fault-tolerant embedding of rings in hypercubes. Journal of Parallel and Distributed Computing, 1991, 11: 63–71
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
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
Chang C-P, Wang J-N, Hsu L-H. Topological properties of twisted cube. Information Science, 1999, 113: 147–167
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
Chang J-M, Yang J-S. Fault-tolerant cycle embedding in alternating group graphs. Applied Mathematics and Computation, 2008, 197(2): 760–767
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)
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)
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
Chen G H, Hwang S C. Cycle in butterfly graphs. Networks, 2000, 35(2): 161–171
Chen M Y, Shin K G. Processor allocation in an n-cube multiprocessor using gray codes. IEEE Transactions on Computers, 1987, 36: 1396–1407
Chen X-B. Cycles passing through prescribed edges in a hypercube with some faulty edges. Information Processing Letters, 2007, 104(6): 211–215
Chen X-B. Some results on topological properties of folded hypercubes. Information Processing Letters, DOI: 10.1016/j.ipl.2008.12.005
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
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
Cheng E, Lipman M. Fault tolerant routing in split-stars and alternating group graphs. Congressus Numerantium, 1999, 139: 21–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
Cheng E, Lipman M-J, Park H. Super connectivity of star graphs, alternating group graphs and split-stars. Ars Combinatoria, 2001, 59: 107–116
Chiang W K, Chen R J. The (n, k)-star graphs: A generalized star graph. Information Processing Letters, 1995, 56: 259–264
Chiang W K, Chen R J. On the arrangement graph. Information Processing Letters, 1998, 66: 215–219
Choudum S A, Sunitha V. Wide-diameter of augmented cubes. Technical Report. Department of Mathematics, Indian Institute of Technology Madras, Chennai, November 2000
Choudum S A, Sunitha V. Automorphisms of augmented cubes. Technical Report. Department of Mathematics, Indian Institute of Technology Madras, Chennai, March 2001
Choudum S A, Sunitha V. Augmented cubes. Networks, 2002, 40(2): 71–84
Cull P, Larson S M. The Möbius cubes. IEEE Transactions on Computers, 1995, 44(5): 647–659
Cull P, Larson S M. On generalized twisted cubes. Information Processing Letters, 1995, 55: 53–55
Day K, Tripathi A. Arrangement graphs: A class of generalized star graphs. Information Processing Letters, 1992, 42(5): 235–241
Day K, Tripathi A. Embedding of cycles in arrangement graphs. IEEE Transactions on Computers, 1993, 42(8): 1002–1006
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
Efe K. A variation on the hypercube with lower diameter. IEEE Transactions on Computers, 1991, 40(11): 1312–1316
El-Amawy A, Latifi S. Properties and performance of folded hypercubes. IEEE Transactions on Parallel and Distributed Systems, 1991, 2(3): 31–42
Esfahanian A H. Generalized measures of fault tolerance with application to n-cube networks. IEEE Transactions on Computers, 1989, 38(11): 1586–1591
Fan J. Hamilton-connectivity and cycle-embedding of the Möbius cubes. Information Processing Letters, 2002, 82: 113–117
Fan J, Jia X, Lin X. Complete path embeddings in crossed cubes. Information Sciences, 2006, 176(22): 3332–3346
Fan J, Lin X, Jia X. Node-pancyclicity and edge-pancyclicity of crossed cubes. Information Processing Letters, 2005, 93(3): 133–138
Fan J, Lin X, Jia X. Optimal path embedding in crossed cubes. IEEE Transactions on Parallel and Distributed Systems, 2005, 16(12): 1190–1200
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
Fan J, Lin X, Jia X, Lau R W H. Edge-pancyclicity of twisted cubes. Lecture Notes in Computer Science, 2005, 3827: 1090–1099
Fu J-S. Fault-tolerant cycle embedding in the hypercube. Parallel Computing, 2003, 29: 821–832
Fu J-S. Longest fault-free paths in hypercubes with vertex faults. Information Sciences, 2006, 176: 759–771
Fu J-S. Conditional fault-tolerant hamiltonicity of star graphs. Parallel Computing, 2007, 33: 488–496
Fu J-S. Fault-free cycles in folded hypercubes with more faulty elements. Information Processing Letters, 2008, 108(5): 261–263
Fu J-S. Fault-free hamiltonian cycles in twisted cubes with conditional link faults. Theoretical Computer Science, 2008, 407(1–3): 318–329
Germa A, Heydemann M C, Sotteau D. Cycles in the cube-connected cycles graphs. Discrete Applied Mathematics, 1998, 83: 135–155
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
Harary F, Lewinter M. Hypercubes and other recursively defined Hamilton laceable graphs. Congressus Numerantium, 1987, 60: 81–84
Heydari M H, Sudborough I H. On the diameter of the pancake network. Journal of Algorithms, 1997, 25: 67–94
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
Hobbs A. The square of a block is vertex pancyclic. Journal of Combinatorical Theory, B, 1976, 20(1): 1–4
Hsieh S-Y. Embedding longest fault-free paths onto star graphs with more vertex faults. Theoretical Computer Science, 2005, 337(1–3): 370–378
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
Hsieh S-Y. Some edge-fault-tolerant properties of the folded hypercube. Networks, 2008, 52(2): 92–101
Hsieh S-Y. A note on cycle embedding in folded hypercubes with faulty elements. Information Processing Letters, 2008, 108(2): 81
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
Hsieh S-Y, Chen C-H. Pancyclicity on Möbius cubes with maximal edge faults. Parallel Computing, 2004, 30(3): 407–421
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
Hsieh S-Y, Chen G-H, Ho C-W. Hamiltonian-laceability of star graphs. Networks, 2000, 36(4): 225–232
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
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
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
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
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
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
Hsieh S-Y, Lin T-J. Panconnectivity and edge-pancyclicity of k-ary n-cubes. Networks, DOI: 10.1002/net.20290
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
Hsieh S-Y, Shen T-H. Edge-bipancyclicity of a hypercube with faulty vertices and edges. Discrete Applied Mathematics, 2008, 156(10): 1802–1808
Hsieh S-Y, Shiu J-Y. Cycle embedding of augmented cubes. Applied Mathematics and Computation, 2007, 191: 314–319
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
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
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
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
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
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
Huang K, Wu J. Area efficient layout of balanced hypercubes. Int’1 J High Speed Electronics and Systems, 1995, 6(4): 631–646
Huang S-C, Chen C-H. Cycles in butterfly graphs. Networks, 2000, 35: 1–11
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
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
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
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
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
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
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
Jwo J S, Lakshmivarahan S, Dhall S K. Embedding of cycles and grids in star graphs. J Circuits Syst Computers, 1991, 1: 43–74
Jwo J S, Lakshmivarahan S, Dhall S K. A new class of interconnection networks based on the alternating group. Networks, 1993, 33: 315–326
Kanevsky A, Feng C. On the embedding of cycles in pancake graphs. Parallel Computing, 1995, 21: 923–936
Kikuchi Y, Araki T. Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs. Information Processing Letters, 2006, 100(2): 52–59
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
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
Kulasinghe P, Bettayeb S. Multiply-twisted hypercube with five of more dimensions is not vertex-transitive. Information Processing Letters, 1995, 53: 33–36
Latifi S, Zheng S, Bagherzadeh N. Optimal ring embedding in hypercubes with faulty links. In: Proc Fault-Tolerant Computing Symp. 1992, 178–184
Leighton F T. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. San Mateo: Morgan Kaufman, 1992
Lewinter M, Widulski W. Hyper-Hamilton laceable and caterpillar-spannable product graphs. Computers and Mathematics with Applications, 1997, 34(1): 99–104
Leu Y-R, Kuo S Y. Distributed fault-tolerant ring embedding and reconfiguration in hypercubes. IEEE Transactions on Computers, 1999, 48(1): 81–88
Li T-K. Cycle embedding in star graphs with edge faults. Applied Mathematics and Computation, 2005, 167(2): 891–900
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
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
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
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
Ma M-J, Liu G-Z, Pan X-F. Path embedding in faulty hypercubes. Applied Mathematics and Computation, 2007, 192(1): 233–238
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
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
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
Ma M-J, Xu J-M. Panconnectivity of locally twisted cubes. Applied Mathematics Letters, 2006, 19(7): 681–685
Ma M-J, Xu J-M. Weak edge-pancyclicity of locally twisted cubes. Ars Combinatoria, 2008, 89: 89–94
Ma M-J, Xu J-M. Transitivity and panconnectivity of folded hypercubes. Ars Combinatoria (to appear)
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
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
Ore O. Hamilton connected graphs. Journal de Mathématiques Pures et Appliquées, 1963, 42(9): 21–27
Park C D, Chwa K Y. Hamiltonian properties on the class of hypercube-like networks. Information Processing Letters, 2004, 91(1): 11–17
Park J-H, Chwa K-Y. Recursive circulants and their embeddings among hypercubes. Theoretical Computer Science, 2000, 244: 35–62
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
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
Saad Y, Schultz M H. Topological properties of hypercubes. IEEE Transactions on Computers, 1988, 37(7): 867–872
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
Sengupta A. On ring in hypercubes with faulty nodes and links. Information Processing Letters, 1998, 68: 207–214
Shih L-M, Tan J J M, Hsu L-H. Edge-bipancyclicity of conditional faulty hypercubes. Information Processing Letters, 2007, 105(1): 20–25
Simmons G. Almost all n-dimensional rectangular lattices are Hamilton laceable. Congressus Numerantium, 1978, 21: 103–108
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
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
Tchuente M. Generation of permutations by graphical exchanges. Ars Combinatoria, 1982, 14: 115–122
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
Tsai C H. Linear array and ring embeddings in conditional faulty hypercubes. Theoretical Computer Science, 2004, 314(3): 431–443
Tsai C-H. Embedding various even cycles in the hypercube with mixed link and node failures. Applied Mathematics Letters, 2008, 21(8): 855–860
Tsai C-H, Jiang S-Y. Path bipancyclicity of hypercubes. Information Processing Letters, 2007, 101(3): 93–97
Tsai C-H, Lai Y-C. Conditional edge-fault-tolerant edge-bipancyclicity of hypercubes. Information Sciences, 2007, 177(24): 5590–5597
Tsai C H, Liang T, Hsu L-H, Lin M-Y. Cycle embedding a faulty wrapped butterfly graphs. Networks, 2003, 42(2): 85–96
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
Tsai P-Y, Chen G-H, Fu J-S. Edge-fault-tolerant pancyclicity of alternating group graphs. Networks, DOI: 10.1002/net.20291
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
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
Tseng Y-C. Embedding a ring in a hypercube with both faulty links and faulty nodes. Information Processing Letters, 1996, 59: 217–222
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
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
Wang D-J. Embedding hamiltonian cycles into folded hypercubes with faulty links. Journal of Parallel and Distributed Computing, 2001, 61: 545–564
Wang H-L, Wang J-W, Xu J-M. Edge-fault-tolerant bipanconnectivity of hypercubes. Information Science, 2009, 179(4): 404–409
Wang W-W, Ma M-J, Xu J-M. Fault-tolerant pancyclicity of augmented cubes. Information Processing Letters, 2007, 103(2): 52–56
Williamson J E. Panconnected graphs II. Periodica Mathematica Hungarica, 1977, 8(2): 105–116
Wu J, Huang K. The balanced hypercubes: A cube-based system for fault-tolerant applications. IEEE Transactions on Computers, 1997, 46(4): 484–490
Xu J-M. Topological Structure and Analysis of Interconnection Networks. Dordrecht/Boston/London: Kluwer Academic Publishers, 2001
Xu J-M, Du Z-Z, Xu M. Edge-fault-tolerant edge-bipancyclicity of hypercubes. Information Processing Letters, 2005, 96(4): 146–150
Xu J-M, Ma M-J. Cycles in folded hypercubes. Applied Mathematics Letters, 2006, 19(2): 140–145
Xu J-M, Ma M-J, Lu M. Paths in Möbius cubes and crossed cubes. Information Processing Letters, 2006, 97(3): 94–97
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
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
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
Xu M, Xu J-M. Edge-pancyclicity of Möbius cubes. Information Processing Letters, 2005, 96(4): 136–140
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
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
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
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
Yang X F, Evans D J, Megson G M. The locally twisted cubes. International Journal of Computer Mathematics, 2005, 82(4): 401–413
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
Yang X F, Megson G M, Evans D J. Locally twisted cubes are 4-pancyclic. Applied Mathematics Letters, 2004, 17: 919–925
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
Author information
Authors and Affiliations
Corresponding author
Rights 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
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11464-009-0017-5