Path embedding in faulty locally twisted cubes
Yuejuan Han, Jianxi Fan, Jiwen Yang, Peide Qian · 2009
As a newly introduced interconnection network for parallel computing, the locally twisted cube possesses many desirable properties. In this paper, fault-tolerant embedding of paths in locally twisted cubes is studied. Let LTQn(V,E) denotes the n-dimensional locally twisted cube. We find that, for any faulty set F ⊂ V (LTQn)∪E(LTQn) with |F| ≤ n - 3 and ℓ with 2n-1−1 ≤ ℓ ≤ |V (LTQn−F)| − 1 for any integer n ≥ 3, a path of length ℓ can be embedded between any two distinct nodes with dilation 1 in LTQn−F. And, the result does not hold if ℓ ≤ 2n-1−2 or |F| ≥ n - 2, that is, the two bounds are tight. Moreover, this result extends the known result on (n-3)-Hamiltonian connectivity of LTQnin the literature.