On some super fault-tolerant Hamiltonian graphs

Abstract

A k-regular Hamiltonian and Hamiltonian connected graph G is super fault-tolerant Hamiltonian if G remains Hamiltonian after removing at most k - 2 nodes and/or edges and remains Hamiltonian connected after removing at most k - 3 nodes and/or edges. A super fault-tolerant Hamiltonian graph has a certain optimal flavor with respect to the fault-tolerant Hamiltonicity and Hamiltonian connectivity. In this paper, we investigate a construction scheme to construct super fault-tolerant Hamiltonian graphs. In particularly, twisted-cubes, crossed-cubes, and Mobius cubes are all special cases of this construction scheme. Therefore, they are all super fault-tolerant Hamiltonian graphs. (C) 2003 Elsevier Inc. All rights reserved.