Locke (Am Math Mon 108:668, 2001) conjectured that the n-dimensional hypercube \(Q_n\) with the set F of 2k removed vertices half from each bipartition set, where \(n \ge k + 2\) and \(k \ge 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 \ge 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 \ge 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 \ge 5\) the graph \(Q_n - V(T)\) is Hamiltonian laceable. Thus our results support Locke hypothesis.
['David Pěgřímek', 'Petr Gregor']
Hamiltonian Laceability of Hypercubes Without Isometric Subgraphs