Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4636978 | Applied Mathematics and Computation | 2006 | 17 Pages |
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 recursive circulant graph is a special case of our construction scheme, and the super fault-tolerant hamiltonian property of recursive circulant graph is obtained.
Related Topics
Physical Sciences and Engineering
Mathematics
Applied Mathematics
Authors
Y-Chuang Chen, Lih-Hsing Hsu, Jimmy J.M. Tan,