Originator(s): Stephen C. Locke (presented by West - REGS 2008)
Background: It is well known (inductively) that the d-dimensional hypercube Qd has a spanning cycle when d≥2. Symmetry by permuting the coordinates shows that it has such a cycle through any edge. Indeed, such symmetry shows that it has such a cycle through any path of length 2.
Conjecture: Let X and Y be the partite sets of Qd. Let S be a vertex set consisting of any k vertices of X and any k vertices of Y. If k&le d-2, then Qd-S contains a spanning cycle (is "Hamiltonian").
Comments: The question was posed by Locke as Problem 10892 in the Monthly, solved only for k=1. The condition on k is obviously necessary, since deleting any d-1 neighbors of a single vertex leaves that vertex present but on no cycle.
Stong [S] gave a short proof for k=1 by proving more generally that a subgraph of the cartesian product C2r×K2 has this property; deleting any two vertices from opposite partite sets leaves a Hamiltonian graph.
Stong [S] partially solved the general question, proving that if d≥2k+3lgk+4, then the deleted hypercube is Hamiltonian.
References:
[L] Stephen C. Locke, Problem 10892, American Mathematical Monthly
(2001), 668.
[S] Richard Stong, Spanning cycles in hypercubes (solution to Problem 10892),
American Mathematical Monthly (2003), May.