A New Non-Asymptotic Upper Bound for Snake-in-the-Box Codes

Abstract

A snake in a graph is a simple cycle without chords. A snake-in-the-box is a snake in the $n$-dimensional cube $Q_n$. Combining the methods of G. Zemor (Combinatorica 17 (1997), 287-298) and of F.I. Solov’eva (Diskret Analiz. 45 (1987), 71-76) a new upper bound for the length of a snake-in-the-box is derived for $16\le n\le 19081$.