A note on the middle levels problem

The middle levels problem consists in determining a hamiltonian cycle in the bipartite Kneser graph B(2k+1,k)B(2k+1,k), also known as the middle levels graph and denoted by BkBk. Previously, it was proved that a particular hamiltonian path in a reduced graph of BkBk implies a hamiltonian cycle in BkBk and a hamiltonian path in the Kneser graph K(2k+1,k)K(2k+1,k). We show that the existence of such a particular hamiltonian path in a reduced graph of K(2k+3,k)K(2k+3,k) implies a hamiltonian path in K(2k+3,k)K(2k+3,k) for k≡1k≡1 or 2(mod3). Moreover, we utilize properties from the middle levels graphs to improve a known algorithm speeding up the search for such a particular hamiltonian path in the reduced graph of BkBk.