Fault-Tolerant Hamiltonicity of Twisted Cubes

✍ Scribed by Wen-Tzeng Huang; Jimmy J.M. Tan; Chun-Nan Hung; Lih-Hsing Hsu

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 185 KB
• Volume: 62
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.2001.1813

✦ Synopsis

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 ) 5 E(TQ n ), we prove that TQ n -F remains hamiltonian if |F| [ n -2. Moreover, we prove that there exists a hamiltonian path in TQ n -F joining any two vertices

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).