On the Construction of Combined k-Fault Tolerant Hamiltonian Graphs ^*

Chun-Nan Hung and Lih-Hsing Hsu ^*
Department of Computer and Information Science
National Chiao Tung University
Hsinchu, Taiwan 300, R.O.C.

Ting-Yi Sung
Institute of Information Science
Academia Sinica
Taipei, Taiwan 115, R.O.C.

Abstract:

A graph G is k-hamiltonian if G - F is hamiltonian for every subset $F \subset (V \cup E)$ with $\vert F\vert \le k$. An n-node k-hamiltonian graph is optimal if it contains the fewest number of edges among all n-node k-hamiltonian graphs. In this paper, we propose a construction scheme for optimal k-hamiltonian graphs with an arbitrary positive integer k. Applying this scheme, we construct a family of optimal k-hamiltonian graphs with diameter $2 \log_{k+1} n - O(1)$, where n is the number of vertices. This diameter is 2 times of Moore bound.

Keywords: hamiltonian cycles, k-hamiltonian graphs, node expansion.