On some super fault-tolerant Hamiltonian graphs

摘要

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 Möbius cubes are all special cases of this construction scheme. Therefore, they are all super fault-tolerant Hamiltonian graphs.