Fault-tolerant hamiltonicity of twisted cubes

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)) boolean AND E(TQ(n)), we prove that TQ(n) - F remains hamiltonian if F less than or equal to n - 2. Moreover, we prove that there exists a hamiltonian path in TQ, - F joining any two vertices u, v in V(TQ(n)) - F if F less than or equal to n-3. The result is optimum in the sense that the fault-tolerant hamiltonicity (fault-tolerant hamiltonian connectivity respectively) of TQn is at most n-2 (n-3 respectively). (C) 2002 Elsevier Science (USA).