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

A hamiltonian graph G=(V,E)G=(V,E) is hamiltonian 1-node-hamiltonian   if G−vG−v is hamiltonian for any v∈Vv∈V. An nn-node hamiltonian 1-node-hamiltonian graph GG is optimal if it contains the least number of edges among all nn-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.