Hamiltonian cycles in hypercubes with 2n-4 faulty edges
In this paper we consider Hamiltonian cycles in hypercubes with faulty edges and present a simple proof that the hypercube Q(n) is not Hamiltonian if it contains a subgraph T such that: (i) exactly half of the vertices in T have parity 0 (the other half have parity 1) and (ii) all edges joining the nodes of parity 0 (or 1) with nodes outside T, are faulty. We will call such a subgraph a trap disconnected halfway. Moreover, we show that for n >= 5, the cube Q(n) with 2n - 4 faulty edges is not Hamiltonian only if it contains a trap T disconnected halfway with T being a subcube of dimension 1 or 2. (C) 2012 Elsevier Inc. All rights reserved.
hamiltonian cycle hypercube fault tolerance local traps