Acta mathematica scientia,Series B ›› 2013, Vol. 33 ›› Issue (1): 227-246.doi: 10.1016/S0252-9602(12)60207-0

• Articles • Previous Articles     Next Articles

PATHS AND CYCLES EMBEDDING ON FAULTY ENHANCED HYPERCUBE NETWORKS

 LIU Min, LIU Hong-Mei   

  1. College of Science, China Three Gorges University, Yichang 443002, China
  • Received:2011-07-07 Revised:2011-11-29 Online:2013-01-20 Published:2013-01-20
  • Supported by:

    This project is supported by NSFC (11071096, 11171129)and NSF of Hubei Province, China (T201103).

Abstract:

Let Qn,k (n ≥ 3, 1≤ kn − 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.

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

CLC Number: 

  • 05C90
Trendmd