VERTEX-FAULT-TOLERANT CYCLES EMBEDDING ON ENHANCED HYPERCUBE NETWORKS

doi:10.1016/S0252-9602(13)60106-X

Acta mathematica scientia,Series B ›› 2013, Vol. 33 ›› Issue (6): 1579-1588.doi: 10.1016/S0252-9602(13)60106-X

• Articles • Previous Articles Next Articles

VERTEX-FAULT-TOLERANT CYCLES EMBEDDING ON ENHANCED HYPERCUBE NETWORKS

ZHANG Yan-Juan*, LIU Hong-Mei, LIU Min

College of Science, China Three Gorges University, Yichang, Hubei Province, 443002, China

Received:2012-06-12 Revised:2012-10-26 Online:2013-11-20 Published:2013-11-20
Contact: ZHANG Yan-Juan，pyyj134@163.com E-mail:pyyj134@163.com; liuhm@ctgu.edu.cn; liumin8989666@126.com
Supported by:
This project is supported by NSFC (11071096 and 11171129) and Hubei Province, China (T201103).

Abstract

Abstract:

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 Q_n,k (n ≥ 3, 1 ≤ k ≤ n − 1)
When |F_v| = 2, we showed that Q_n,k − F_v contains a fault-free cycle of every even length from 4 to 2ⁿ − 4 where n (n ≥3) and k have the same parity; and contains a fault-free cycle of every even length from 4 to 2ⁿ − 4, simultaneously, contains a cycle of every odd length from n−k+2 to 2ⁿ−3 where n (≥3) and k have the different parity. Furthermore, when |F_v| = f_v ≤ n − 2, we prove that there exists the longest fault-free cycle, which is of even length 2ⁿ − 2f_v 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 2ⁿ − 2f_v + 1 in Q_n,k − F_vwhere n (≥3) and k have the different parity.

Key words: enhanced hypercube, fault tolerance, cycles embedding

CLC Number:

05C90

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.

Trendmd

References

[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

VERTEX-FAULT-TOLERANT CYCLES EMBEDDING ON ENHANCED HYPERCUBE NETWORKS

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 1

Metrics

Comments

Recommended 10