Hamiltonicity of hypercubes with faulty vertices

• Locke (2001) conjectured that: If n≥k+2n≥k+2, then n-cube is Hamiltonian by deleting any k vertices from each partite set.
• We show that the conjecture holds if 2k vertices are all the endvertices of k independent edges.
• If n≥k+3n≥k+3, then the n-cube is Hamilton laceable by deleting all the endvertices of k independent edges.

Let QnQn denote the n-dimensional hypercube with the bipartition W and B  . Assume W0={a1,a2,…,ak}⊂WW0={a1,a2,…,ak}⊂W and B0={b1,b2,…,bk}⊂BB0={b1,b2,…,bk}⊂B, where k≥1k≥1 and n≥k+2n≥k+2. The following is a long-standing conjecture (Locke, 2001 [15]): The graph G=Qn−(W0∪B0)G=Qn−(W0∪B0) contains a Hamiltonian cycle. Very recently, Locke' conjecture was proven when k≤4k≤4[3] or n≥2k+2n≥2k+2[14]. In this paper, we obtain the following two results: (1) If aiai is adjacent to bibi for each i   with 1≤i≤k1≤i≤k, then Locke' conjecture holds (2) Moreover, if n≥k+3n≥k+3, then the graph G   is Hamilton laceable, i.e., for any a∈W\W0a∈W\W0 and b∈B\B0b∈B\B0, the graph G contains a Hamiltonian path connecting a and b  , and the lower bound k+3k+3 is optimal. Our results may find some applications.