Acta mathematica scientia, Series B >
VERTEX-FAULT-TOLERANT CYCLES EMBEDDING ON ENHANCED HYPERCUBE NETWORKS
Received date: 2012-06-12
Revised date: 2012-10-26
Online published: 2013-11-20
Supported by
This project is supported by NSFC (11071096 and 11171129) and Hubei Province, China (T201103).
In this paper, we study the enhanced hypercube, an attractive variant of the hypercube and obtained by adding some complementary edges from a hypercube, and focus on cycles embedding on the enhanced hypercube with faulty vertices. Let Fv be the set of faulty vertices in the n-dimensional enhanced hypercube Qn,k (n ≥ 3, 1 ≤ k ≤ n − 1)
When |Fv| = 2, we showed that Qn,k − Fv contains a fault-free cycle of every even length from 4 to 2n − 4 where n (n ≥3) and k have the same parity; and contains a fault-free cycle of every even length from 4 to 2n − 4, simultaneously, contains a cycle of every odd length from n−k+2 to 2n−3 where n (≥3) and k have the different parity. Furthermore, when |Fv| = fv ≤ n − 2, we prove that there exists the longest fault-free cycle, which is of even length 2n − 2fv whether n (n ≥3) and k have the same parity or not; and there exists the longest fault-free cycle, which is of odd length 2n − 2fv + 1 in Qn,k − Fv where n (≥3) and k have the different parity.
Key words： enhanced hypercube; fault tolerance; cycles embedding
ZHANG Yan-Juan , LIU Hong-Mei , LIU Min . VERTEX-FAULT-TOLERANT CYCLES EMBEDDING ON ENHANCED HYPERCUBE NETWORKS[J]. Acta mathematica scientia, Series B, 2013 , 33(6) : 1579 -1588 . DOI: 10.1016/S0252-9602(13)60106-X
[1] Bondy J A, Murty U S R. Graph Theory with Application Networks. London: Kluwer Academic Publish-ers, 1976
[2] Tsai C H. Fault-tolerant cycles embedded in hypercubes with mixed link and node failures. Appl Math Lett, 2008, 21: 855–860
[3] 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
[4] Tsai C H, Tan J M, Liang T, Hsu L H. Fault-tolerant hamiltonian laceability of hypercubes. Inform Process Lett, 2002, 83: 301–306
[5] Tsai C H. Cycles embedding in hypercubes with node failures. Inform Process Lett, 2007, 102: 242–246
[6] Saad Y, Schultz M H. Topological of hypercubes. IEEE Trans Comput, 1988, 37(7): 867–872
[7] Hsieh S Y. Fault-tolerant cycles embedding in the hypercube with both faulty vertices and faulty edges. Parallel Comput, 2006, 32: 84–91
[8] Tzeng N F, Wei S. Enhanced hypercube. IEEE Transactions on Computer, 1991, 3: 284–294
[9] Liu H M. The structural features of enhanced hypercube networks. The 5th International Conference on Natural Computation, 2009: 345–348
[10] Liu HM. Properties and performance of enhanced hypercube networks. J Systems Science and Information, 2006, 3: 251–256
[11] Liu H M. The construction of disjoint paths in folded hypercube. J Systems Science and Informance, 2010, 8: 97–102
[12] Hsieh S Y, Kuo C N, Huang H L. 1-vertex-fault-tolerant cycles embedding on folded hypercubes. Discrete Appl Math, 2009, 157: 3094–3098
[13] Wang D. Embedding hamiltonian cycles into folded hypercubes with faulty links. Parallel Distr Comput, 2001, 61: 545–564
[14] Choudum S A, Nandini R U. Complete binary trees in folded and enhanced cube. Networks, 2004, 43: 226–272
[15] Leighton F T. Introduction to Parallel Algorithms and Architecture: Arrays, Trees, Hypercubes. San Mateo, CA: Morgan Kaufmann, 1992
[16] Xu J M, Ma M J. A survey on cycle and path embedding in some networks. Frontiers of Mathematics in China, 2009, 4(2): 217–252
[17] Xu J M, Du Z Z, Xu M. Edge-fault-tolerant edge-bipancyclicity of hypercubes. Inform Process Lett, 2005, 96(4): 146–150
[18] Fu J S. Fault-tolerant cycles embedding in the hypercube. Parallel Comput, 2003, 29: 821–832
[19] Chang NW, Hsieh S Y. Fault-tolerant bipancyclicity of faulty hypercubes under the generalized conditional-fault model. IEEE Trans Comm, 2011, 59(12): 3400–3409
[20] Huang C W, Huang H L, Hsieh S Y. Edge-bipancyclicity of star graphs with faulty elements. Theoretical Computer Science, 2011, 412(50): 6938–6947
[21] Kuo C N, Hsieh S Y. Pancyclicity and bipancyclicity of conditional faulty folded hypercubes. Information Sciences, 2010, 180(15): 2904–2914
[22] Hsieh S Y, Lee C W. Pancyclicity of restricted hypercube-like networks under the conditional fault model. SIAM J Discrete Math, 2010, 23(4): 2010–2019
[23] Hsieh S Y, Lee C W. Conditional edge-fault hamiltonicity of matching composition networks. IEEE Trans Parall Distr Sys, 2009, 20(4): 581–592
[24] Liu H M, Liu M. Paths and cycles embedding on faulty enhanced hypercube networks. Acta Math Sci, 2013, 33B(1): 227–246
/
| 〈 |
|
〉 |