Hamiltonian cycles in hypercubes with more faulty edges
Jing Li, Di Liu, Xiaohui Gao · International Journal of Computer Mathematics · 2016
The hypercube Qn is one of the best known interconnection networks for parallel and distributed systems. In this paper we consider hamiltonian cycles in hypercubes Qn (n≥6) with faulty edges. It is proved that there still exists a fault-free hamiltonian cycle in the hypercube with 3n−7 faulty edges if the following two conditions are satisfied: (1) the degree of every vertex is at least two, (2) there do not exist a forbidden f4-cycle or f6-cycle. Our result is optimal in some sense.