Conditional edge-fault hamiltonian-connectivity of restricted hypercube-like networks

A graph G is considered conditional k-edge-fault hamiltonian-connected if, after k faulty edges are removed from G, under the assumption that each node is incident to at least three fault-free edges, a hamiltonian path exists between any two distinct nodes in the resulting graph. This paper focuses on the conditional edge-fault hamiltonian-connectivity of a wide class of interconnection networks called restricted hypercube-like networks (RHLs). An n-dimensional RHL (RHL_n) is proved to be conditional (2n−7)-edge-fault hamiltonian-connected for n≥5. The technical theorem proposed in this paper is then applied to show that several multiprocessor systems, including n-dimensional crossed cubes, n-dimensional twisted cubes for odd n, n-dimensional locally twisted cubes, n-dimensional generalized twisted cubes, n-dimensional Möbius cubes, and recursive circulants G(2ⁿ,4) for odd n, are all conditional (2n−7)-edge-fault hamiltonian-connected.