On the construction of combinedk‐fault‐tolerant Hamiltonian graphs
Chun‐Nan Hung, Lih‐Hsing Hsu, Ting‐Yi Sung · Networks · 2001
Abstract A graphGis a combinedk‐fault‐tolerant Hamiltonian graph (also called a combinedk‐Hamiltonian graph) ifG−Fis Hamiltonian for every subsetF⊂ (V(G) ∪E(G)) with |F| =k. A combinedk‐Hamiltonian graphGwith |V(G)| =nis optimal if it has the minimum number of edges among alln‐nodek‐Hamiltonian graphs. Using the concept of node expansion, we present a powerful construction scheme to construct a larger combinedk‐Hamiltonian graph from a given smaller graph. Many previous graphs can be constructed by the concept of node expansion. We also show that our construction maintains the optimality property in most cases. The classes of optimal combinedk‐Hamiltonian graphs that we constructed are shown to have a very good diameter. In particular, those optimal combined 1‐Hamiltonian graphs that we constructed have a much smaller diameter than that of those constructed previously by Mukhopadhyaya and Sinha, Harary and Hayes, and Wang et al. © 2001 John Wiley & Sons, Inc.