A snake is an Eulerian path in the -hypercube that has no chords
(i.e., any hypercube edge joining snake vertices is
a snake edge). Klee (1970) asked for the maximum length of a -snake.
Klee (1970) gave the bounds
(1)
for (Danzer and Klee 1967, Douglas
1969), as well as numerous references. Abbott and Katchalski (1988) show
(2)
and Snevily (1994) showed that
(3)
for , and conjectured
(4)
for . The first few values for for , 2, ..., are 2, 4, 6, 8, 14, 26, ... (OEIS A000937).
Abbott, H. L. and Katchalski, M. "On the Snake in the Box Problem." J. Combin. Th. Ser. B44, 12-24, 1988.Danzer,
L. and Klee, V. "Length of Snakes in Boxes." J. Combin. Th.2,
258-265, 1967.Douglas, R. J. "Some Results on the Maximum
Length of Circuits of Spread
in the -Cube." J. Combin. Th.6,
323-339, 1969.Emelianov, P. "Snake-in-the-Box." http://mix.nsk.ru/epg/snake.html.Evdokimov,
A. A. "Maximal Length of a Chain in a Unit -Dimensional Cube." Mat. Zametki6, 309-319,
1969.Guy, R. K. "Unsolved Problems Come of Age." Amer.
Math. Monthly96, 903-909, 1989.Guy, R. K. "Monthly
Unsolved Problems." Amer. Math. Monthly94, 961-970, 1989.Guy,
R. K. and Nowakowski, R. J. "Monthly Unsolved Problems, 1696-1995."
Amer. Math. Monthly102, 921-926, 1995.Kautz, W. H.
"Unit-Distance Error-Checking Codes." IRE Trans. Elect. Comput.7,
177-180, 1958.Klee, V. "What is the Maximum Length of a -Dimensional Snake?" Amer. Math. Monthly77,
63-65, 1970.Sloane, N. J. A. Sequence A000937/M0995
in "The On-Line Encyclopedia of Integer Sequences."Snevily,
H. S. "The Snake-in-the-Box Problem: A New Upper Bound." Disc.
Math.133, 307-314, 1994.Solov'jeva, F. I. "An
Upper Bound for the Length of a Cycle in an -Dimensional Cube." Diskret. Analiz.45,
1987.