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 TQn(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(TQn)∪E(TQn) with |F|⩽n-3 and any integer l with 2n-1-1⩽l⩽|V(TQn-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⩽2n-1-2 or |F|⩾n-2. We also extend the result on (n-3)-Hamiltonian connectivity of TQn in the literature.