Middle levels problem
The graph is known as the middle-levels graph because it may be thought of as the graph formed by the cover relations between the middle two layers of the Hasse diagram of the Boolean lattice of all subsets of a -element set, partially ordered by inclusion. The conjecture has been computationally verified up to [AS] (Announced only at end of paper). It is also known that contains a cycle containing at least of its vertices [J] and that is Hamiltonian [HKRR].
[HKRR] Peter Horák, Tomáš Kaiser, Moshe Rosenfeld, Zdeněk Ryjáček, The prism over the middle-levels graph is Hamiltonian, Order 22 (2005), no. 1, 73--81.
[J] Robert J. Johnson, Long cycles in the middle two layers of the discrete cube. J. Combin. Theory Ser. A 105 (2004), no. 2, 255--271. MathSciNet
[SW] Carla D. Savage and Peter Winkler, Monotone Gray codes and the middle levels problem, J. Combin. Theory Ser. A 70 (1995), no. 2, 230--248.
[SSS] Ian Shields, Brendan J. Shields, Carla D. Savage, An update on the middle levels problem, preprint.
[AS] Kazuyuki Amano, Manabu Shimada, A Note on the Middle Levels Conjecture, preprint.
* indicates original appearance(s) of problem.