Hamiltonian cycles in hypercubes with faulty edges

摘要

Szepietowski [12] observed that the hypercube Q_n is not Hamiltonian if it contains a trap disconnected halfway. A proper subgraph T is disconnected halfway if at least half of its nodes have parity 0 (or 1, resp.) and all edges joining the nodes of parity 0 (or 1, resp.) in T with nodes outside T, are faulty. In this paper, we describe all traps disconnected halfway T with the size |T| < 8 and we consider the problem whether there exist small sets of faulty edges that are not based on sets disconnected halfway and still preclude Hamiltonian cycles. We show that if Q_n with the set of faulty edges F contains a trap disconnected halfway T that is of size |T| ≤ 8 and is minimal, then T is a path P_2 or is Hamiltonian. We also describe heuristic that recognizes nonhamiltonian cubes, also these ones that do not contain traps disconnected halfway.