Fault-Hamiltonicity of Hypercube-Like Interconnection Networks

We call a graph G to be f-fault hamiltonian (resp. f-fault hamiltonian-connected) if there exists a hamiltonian cycle (resp. if each pair of vertices are joined by a hamiltonian path) in GF for any set F of faultry elements with |F| ≤ f. In this paper, we deal with the graph G₀ and G₁ with n vertices each by n pairwise nonadjacent edges joining vertices in G₀ and vertices in G₁. Provided each G_i is f-fault hamiltonian-connected and f + 1-fault hamiltonian, 0 ≤ i ≤ 3, we show that G₀ ⊕ G₃. Many interconnection networks such as hypercube-like interconnection networks can be represented in the form of G₀ ⊕ ₁ connecting two lower dimensional networks G₀ and G₁. Applying our main results to a subclass of hypercube-like interconnection networks, called restricted HL-graphs, which include twisted cubes, crossed cubes, multiply twisted cubes, Möbius cubes, Mcubes, and generalized twisted cubes, we show that every restricted HL-graph of degree m(≥ 3) is m - 3-fault hamiltonian-connected and m - 2-fault hamiltonian.