Survey on path and cycle embedding in some networks

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.

Keywords

Cycle / path / pancyclicity / hamiltonicity / panconnectivity / faulttolerance / hypercube-like network / embedding

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

[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

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

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

[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

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

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

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

[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

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

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

[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

[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

[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

[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

[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

[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

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

[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)

[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)

[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

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

[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

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

[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

[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

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

[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

[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

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

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

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

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

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

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

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

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

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

[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

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

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

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

[47] Fan J. Hamilton-connectivity and cycle-embedding of the M�obius cubes. Information Processing Letters, 2002, 82: 113-117

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

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

[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

[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

[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

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

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

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

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

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

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

[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

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

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

[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

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

[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

[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

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

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

[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

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

[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

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

[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

[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

[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

[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

[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

[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

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

[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

[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

[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

[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

[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

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

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

[90] Huang W-T, Chen W-K, Chen C-H. Pancyclicity of M¨obius 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

[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

[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

[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

[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

[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

[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

[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

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

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

[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

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

[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

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

[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

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

[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

[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

[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

[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

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

[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

[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

[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

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

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

[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

[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

[122] Ore O. Hamilton connected graphs. Journal de Math' ematiques Pures et Appliqu'ees, 1963, 42(9): 21-27

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

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

[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

[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

[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

[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

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

[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

[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

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

[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

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

[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

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

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

[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

[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

[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

[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

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

[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

[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

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

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

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

[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

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

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

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

[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

[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

[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

[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

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

[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

[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

[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

[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

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

[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

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

[168] Yang X F, Megson G M, Evans D J. Pancyclicity of M¨obius cubes with faulty nodes. Microprocessors and Microsystems, 2006, 30(3): 165-172

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg