The snake-in-the-box problem: A new upper bound (Q1336714)

The \(n\)-cube \(Q^ n\) is the graph whose vertices are labeled by the binary \(n\)-tuples and such that two vertices are adjacent if and only if their corresponding \(n\)-tuples differ in precisely one position. In this paper, the author shows that if \(S\) is the longest cycle in \(Q^ n\), then \(| S|\leq 2^{n-1}- 2^{n-2}/(20n- 41)\) for \(n\geq 12\), where \(| S|\) is the number of vertices in \(S\). This new upper bound improves the earlier bound of \textit{F. I. Solov'eva} [Metody Diskretn. Anal. 45, 71-76 (1987; Zbl 0707.05040)].