A recursively construction scheme for super fault-tolerant hamiltonian graphs

Abstract

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 recursire circulant graph is a special case of our construction scheme. and the super fault-tolerant hamiltonian property of recursive circulant graph is obtained. (c) 2005 Elsevier Inc. All rights reserved.