Two construction schemes for cubic hamiltonian 1-node-hamiltonian graphs

A hamiltonian graph G = ( V , E ) is hamiltonian 1-node-hamiltonian if G − v is hamiltonian for any v ∈ V . An n -node hamiltonian 1-node-hamiltonian graph G is optimal if it contains the least number of edges among all n -node hamiltonian 1-node-hamiltonian graphs. The study of optimal 1-node-hamiltonian graphs is motivated by the design of optimal fault-tolerant token rings in computer networks. It is known that every cubic hamiltonian 1-node-hamiltonian graph is optimal. In this paper, we propose two construction schemes for cubic hamiltonian 1-node-hamiltonian regular graphs.