ABSTRACT
From previous discussions, we have several methods that recursively construct kregular (k− 2)-fault-tolerant Hamiltonian graphs for large k. Thus, we should put some effort on k-regular (k− 2)-fault-tolerant Hamiltonian graphs for small k. A lot of optimal 1-Hamiltonian graphs have been proposed [140,182,256,333,335]. For any 1-Hamiltonian regular graph, it is proved that the graph is optimal if and only if the graph is 3-regular [183,334]. In this chapter, we are interested only in optimal 1Hamiltonian regular graphs. Families of optimal 1-Hamiltonian regular graphs were proposed by Harary and Hayes [139,140], Mukhopadhyaya and Shani [256], Wang, Hung, andHsu [333], andHung, Hsu, and Sung [183]. From themathematical point of view, it would be interesting to characterize all optimal 1-Hamiltonian regular graphs. One strategy to characterize all optimal 1-Hamiltonian regular graphs is to find some basic graphs and construction schemes with the hope that we can construct all optimal 1-Hamiltonian regular graphs. We also hope that these basic graphs and construction schemes are as simple as possible.
