Acta mathematica scientia, Series B >
PATHS AND CYCLES EMBEDDING ON FAULTY ENHANCED HYPERCUBE NETWORKS
Received date: 2011-07-07
Revised date: 2011-11-29
Online published: 2013-01-20
Supported by
This project is supported by NSFC (11071096, 11171129)and NSF of Hubei Province, China (T201103).
Let Qn,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−2fv−1 (respectively, 2n−2fv−2) can be embedded on Qn,k with fv+fe ≤ n−1 when dQn,k (u, v) is odd (respectively, dQn,k (u, v) is even). Secondly, an Qn,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 − 2fv can be embedded on Qn,k with fe ≤ n − 1 and fv + fe ≤ 2n − 4.
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 . DOI: 10.1016/S0252-9602(12)60207-0
[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
/
| 〈 |
|
〉 |