Hamiltonian cycles in hypercubes with faulty edges. Issue 4 (2nd October 2018) - Dybizbański, Janusz; Szepietowski, Andrzej
ABSTRACT: Szepietowski [12] observed that the hypercube 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 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 with the set of faulty edges F contains a trap disconnected halfway T that is of size and is minimal, then T is a path or is Hamiltonian. We also describe heuristic that recognizes nonhamiltonian cubes, also these ones that do not contain traps disconnected halfway.