Abstract
Locke conjectured that the n-dimensional hypercube Q(n) with the set F of 2k removed vertices half from each bipartition set, where n >= k + 2 and k > 1, is Hamiltonian. So far the conjecture remains open although partial results are known; some of them with additional conditions on the set F.
We explore Hamiltonian properties of Q(n) - F if the set of faulty vertices F forms either an isometric cycle of Q(n) or an isometric tree of Q(n). We study a more general problem.
A bipartite graph G is Hamiltonian laceable if either (a) its bipartition sets are of equal size and for each pair of vertices x, y from different bipartition sets there exists a Hamiltonian path between x and y, or (b) its bipartition sets differ in sizes by one and for each pair of vertices x, y from the larger bipartition set there exists a Hamiltonian path between x and y. In particular, we show that if C is an isometric cycle in Q(n) for n >= 5, then Q(n) - V(C) is Hamiltonian laceable.
This allows us to remove up to 2n faulty vertices. Furthermore, if T is balanced isometric tree in Q(n), then for n >= 4 the graph Q(n) - V(T) is Hamiltonian laceable.
Finally, if T is an almost-balanced isometric tree in Q(n), then for n >= 5 the graph Q(n) - V(T) is Hamiltonian laceable. Thus our results support Locke hypothesis.