A Census of New Snake-in-the-Box Records
arXiv:2607.15270
summary
The paper presents new longest induced (chordless) paths, called snakes, in hypercube graphs for dimensions 9 through 13, thereby improving the known lower bounds for the snake-in-the-box problem and providing a verifiable dataset of these record-length paths.
Abstract
The snake-in-the-box problem, introduced by Kautz in 1958, asks for the longest induced (chordless) path, called a snake, in the hypercube graph . The maximum length is known in each dimension . We give snakes that are longer than the previous best-known in every dimension from to , improving the lower bound on . All record-length paths are provided in a computer-verifiable dataset.
Updated to include new records. 5 pages
Topics & keywords
#snake-in-the-box#hypercube graphs#induced paths#combinatorial optimization#coding theory#lower boundssnake-in-the-boxhypercubeinduced chordless pathlower boundcomputational searchrecord-length snakes