PATHS AND CYCLES EMBEDDING ON FAULTY ENHANCED HYPERCUBE NETWORKS

doi:10.1016/S0252-9602(12)60207-0

Abstract

Abstract:

Let Q_n,k(n ≥ 3, 1≤ k≤ n − 1) be an n-dimensional enhanced hypercube which is an attractive variant of the hypercube and can be obtained by adding some com-plementary edges, fv and fe be the numbers of faulty vertices and faulty edges, respectively. In this paper, we give three main results. First, a fault-free path P[u, v] of length at least 2n−2f_v−1 (respectively, 2n−2f_v−2) can be embedded on Qn,k with f_v+f_e ≤ n−1 when dQn,k (u, v) is odd (respectively, d_Qn,k (u, v) is even). Secondly, an Q_n,k is (n − 2) edge-fault-free hyper Hamiltonian-laceable when n (≥ 3) and k have the same parity. Lastly, a fault-free cycle of length at least 2n − 2f_v can be embedded on Q_n,k with fe ≤ n − 1 and f_v + f_e≤ 2n − 4.

Key words: enhanced hypercube, fault-tolerant embedding, paths embedding, cycles em-bedding, Hamiltonian-laceability

CLC Number:

05C90

LIU Min, LIU Hong-Mei. PATHS AND CYCLES EMBEDDING ON FAULTY ENHANCED HYPERCUBE NETWORKS[J].Acta mathematica scientia,Series B, 2013, 33(1): 227-246.

Trendmd

References

[1] Bondy J A, Murty U S R. Graph Theory with Application Networks. London: Kluwer Academic Publish-ers, 1976

[2] Tzeng N F, Wei S. Enhanced hypercube. IEEE Trans Comp, 1991, 3: 284–294

[3] Liu H M. The structural features of enhanced hypercube networks. The 5th International Conference on Natural Computation, 2009: 345–348

[4] Liu H M. Properties and performance of enhanced hypercube networks. J Sys Sci Inform, 2006, 3: 251–256

[5] Liu H M. The construction of disjoint paths in folded hypercube. J Sys Sci Inform, 2010, 8: 97–102

[6] Hsieh S Y. Fault-tolerant cycles embedding in the hypercube with more both faulty vertices and faulty edges. Parallel Computing, 2006, 32: 84–91

[7] Hsieh S Y, Kuo C N. Hamiltonian-connectivity and strongly Hamilition-lacesbility of folded hypercubes. Comput Math Appl, 2007, 53: 1040–1044

[8] Hsieh S Y, Chen G H, Ho C W. Hamilitionaian-laceability of star graph. Networks, 2000, 36: 225–232

[9] S. Y. Hsieh, Some edge-fault-tolerant properties of the folded hypercube. Networks, 2007: 92–101

[10] Li T K, Tsai C H, Tan J M, Hsu L H. Bipanconnectivity and edge-fault-tolerant bipancyclicity of hyper-cubes. Inform Process Lett, 2003, 87: 107–110

[11] Tsai C H, Tan J M, Liang T, Hsu L H. Fault-tolerant Hamiltonian laceability of hypercubes. Inform Process Lett, 2002, 83: 301–306

[12] Tsai C H. Cycles embedding in hypercubes with node failures. Inform Process Lett, 2007, 102: 242–246

[13] Tsai C H. Linear arry and ring embedding in conditional faulty hypercubes. Theoretical Computer Science, 2004, 314: 431–443

[14] Xu J M, Du Z Z, Xu M. Edge-fault-tolerant edge-bipancyclicity of hypercubes. Inform Process Lett, 2005, 96(4): 146–150

[15] Fu J S. Fault-tolerant cycles embedding in the hypercube. Parallel Comput, 2003, 29: 821–832

[16] Fu J S, Chen G H. Hamiltonicity of the hierarchical cubic network. Theory Comput Syst, 2002, 35: 57–79

[17] Liu M, Liu H M. The Edge-Fault-Tolerant Hamiltonian Connectivity of Enhanced Hypercube. Interna-tional Conference on Network Computing and Information Security, 2011, 2: 103–107

[18] Latifi S, Zheng S Q, Bagherzadeh N. Optimal ring embedding in hypercubes with faulty links. Proceedings of the 22 Annual International Symposium on Fault-Tolerant Computing, Boston: MA, 1992: 178–184

[19] Tseng Y C. Embedding a ring in a hypercube with both faulty links and faulty nodes. Informa Proc Lett, 1996, 59: 217–222

[20] Sengupta A. On ring embedding in hypercubes with faulty nodes and links. Inform Process Lett, 1998, 68: 207–214

[21] Wang D. Embedding hamiltonian cycles into folded hypercubes with faulty links. Parallel Distr Comput, 2001, 61: 545–564

[22] Choudum S A, R. Usha Nandini, Complete binary trees in folded and enhanced cube. Networks, 2004, 43: 226–272

[23] Leighton F T. Introduction to Parallel Algorithms and Architecture: Arrays, Trees, Hypercubes. San Mateo, CA: Morgan Kaufmann, 1992

[24] Lewinter M, Widulski W. Hyper Hamiltonian-laceable and caterpillar-spannable product graphs. Comput Math Appl, 1997, 34: 99–104

[25] Simmon G. Almost all n-dimensional retangular lattices are Hamiltonian-laceable. Congressus Numeran-tium, 1978, 21: 103-1-8

[26] Hsieh S Y, Ho C W, Chen G H. Fault-free Hamiltonian cycles in faulty arrangement graphs. IEEE Transactions on Parallel and Distributed Systems, 1999, 10(3): 223–237

[27] Xu J M, Ma M J. A survey on cycle and path embedding in some networks. Front Math China, 2009, 4(2): 217–252

[28] Hsieh S Y, Chang N W. Extended fault-tolerant cycle embedding in faulty hypercubes. IEEE Transactions on Reliability, 2009, 58(4): 702–710

[29] Hsieh S Y, Chang N W. Pancyclicity on the Mobius cube with both faulty nodes and faulty edges. IEEE Transactions on Computers, 2006, 55(7): 845–863

[30] Hsu D F. Interconnection networks and algorithms. Networks, 1993, 23(4) : 211–213

[31] Hsieh S Y. A note on cycle embedding in folded hypercubes with faulty elements. Inform Proces Lett, 2008, 108: 81

[32] Fu J S. Fault-free cycles in folded hypercubes with more faulty elements. Inform Proces Lett, 2008, 108: 261–263

[33] Hsieh S Y, Lee C W. Pancyclicity of restricted hypercube-like networks under the conditional fault model. SIAM J Disc Math, 2010, 23(4): 2010–2019

[34] Hsieh S Y, Lee C W. Conditional edge-fault hamiltonicity of matching composition networks. IEEE Transactions on Parallel and Distributed Syetems, 2009, 20(4): 581–592

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

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

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

[38] Liu H M. Circular chromatic number and mycielski graphs. Acta Math Sci, 2006, 26B(2): 314–320