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 is an element of 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. (c) 2007 Elsevier Ltd. All rights reserved.
hamiltonian 1-node-hamiltonian interconnection network graph theorem hamiltonian cycle fault tolerance