Optimal fault-tolerant embedding of paths in twisted cubes

The twisted cube is an important variation of the hypercube. It possesses many desirable properties for interconnection networks. In this paper, we study fault-tolerant embedding of paths in twisted cubes. Let TQ_n (V, E) denote the n-dimensional twisted cube. We prove that a path of length l can be embedded between any two distinct nodes with dilation 1 for any faulty set F ⊂ V (TQ_n) ∪ E (TQ_n) with | F | ≤ n - 3 and any integer l with 2^{n - 1} - 1 ≤ l ≤ | V (TQ_n - F) | - 1 (n ≥ 3). This result is optimal in the sense that the embedding has the smallest dilation 1. The result is also complete in the sense that the two bounds on path length l and faulty set size | F | for a successful embedding are tight. That is, the result does not hold if l ≤ 2^{n - 1} - 2 or | F | ≥ n - 2. We also extend the result on (n - 3)-Hamiltonian connectivity of TQ_n in the literature. © 2006 Elsevier Inc. All rights reserved.