Construction schemes for fault-tolerant Hamiltonian graphs

Abstract

In this paper, we present three construction schemes for fault-tolerant Hamiltonian graphs. We show that applying these construction schemes on fault-tolerant Hamiltonian graphs generates graphs preserving the original Hamiltonicity property. We apply these construction schemes to generate some known families of optimal 1-Hamiltonian graphs in the literature and the Hamiltonicity properties of these graphs are the direct consequence of the construction schemes. In addition, we can use these construction schemes to propose new family of optimal 1-Hamiltonian graphs. (C) 2000 John Wiley & Sons, Inc.