Fault-Tolerant Hamiltonicity of Twisted Cubes^*

Wen-Tzeng Huang, Jimmy J. M. Tan, Chun-Nan Hung and Lih-Hsing Hsu^*
Department of Computer and Information Science
National Chiao Tung University
Hsinchu, Taiwan 300, R.O.C.

Abstract:

The twisted cube TQ_n is derived by changing some connection of hypercube Q_n according to specific rules. Recently, many topological properties of this variation cube are studied. In this paper, we consider a faulty twisted n-cube with both edge and/or node faults. Let F be a subset of $V(TQ_n) \cup E(TQ_n)$, we prove that TQ_n - F remains hamiltonian if $\vert F\vert \le n-2$. Moreover, we prove that there exists a hamiltonian path in TQ_n-F joining any two vertices u,v in V(TQ_n)-F if $\vert F\vert \le n-3$. The result is optimum in the sense that the fault-tolerant hamiltonicity (fault-tolerant hamiltonian connectivity respectively) of TQ_n is at most n-2 ( n-3 respectively).

Keywords: hamiltonian, hamiltonian connected, fault tolerant, twisted cube.