A recursively construction scheme for super fault-tolerant hamiltonian graphs

摘要

For the interconnection network topology, it is usually represented by a graph. When a network is used, processors and/or links faults may happen. Thus, it is meaningful to consider faulty networks. We consider k-regular graphs in this paper. We define a k-regular hamiltonian and hamiltonian connected graph G is super fault-tolerant hamiltonian if G remains hamiltonian after removing at most k − 2 vertices and/or edges and remains hamiltonian connected after removing at most k − 3 vertices and/or edges. A super fault-tolerant hamiltonian graph has a certain optimal flavor with respect to the fault-tolerant hamiltonicity and fault-tolerant hamiltonian connectivity. The aim of this paper is to investigate a construction scheme to construct various super fault-tolerant hamiltonian graphs. Along the way, the recursive circulant graph is a special case of our construction scheme, and the super fault-tolerant hamiltonian property of recursive circulant graph is obtained.