Hamiltonicity of hypercubes with faulty vertices

Let Q(n) denote the n-dimensional hypercube with the bipartition W and B. Assume W-0 = {a(1), a(2),..., a(k)} subset of W and B-0 = {b(1), b(2),..., b(k)} subset of B, where k >= 1 and n >= k+2. The following is a long-standing conjecture (Locke, 2001 [15]): The graph G = Qn (W-0 U B-0) contains a Hamiltonian cycle. Very recently, Locke' conjecture was proven when k <= 4 [3] or n >= 2k + 2 [14]. In this paper, we obtain the following two results: (1) If a(i) is adjacent to b1 for each i with 1 <= i <= k, then Locke' conjecture holds (2) Moreover, if n >= k + 3, then the graph G is Hamilton laceable, i.e., for any a epsilon W\W-0 and b epsilon B\B-0, the graph G contains a Hamiltonian path connecting a and b, and the lower bound k + 3 is optimal. Our results may find some applications. (C) 2016 Elsevier B.V. All rights reserved.