Conditional edge-fault-tolerant Hamiltonicity of enhanced hypercube
Min Liu, Hongmei Liu · 2011
The architecture of an interconnection network is usually represented by a graph, and a graph G is Hamiltonian if it has a Hamiltonian cycle which traverses every node of G exactly once. In this article, we analyze the conditional edge-fault Hamiltonicity of the enhanced hypercube, which is an attractive variant of hypercube and can be obtained by adding some complementary edges. For any n-dimensional (n ≥ 3) enhanced hypercube with at most (2n - 3) faulty edges in which each vertex is incident with at least two fault-free edges, we showed that there exists a fault-free Hamiltonian cycle.