On the snake in the box problem

DOI10.1016/0095-8956(88)90051-2MaRDI QIDQ1113920zbMATH OpenOpenAlexFDO

Authors H. L. Abbott, Meir Katchalski

Publication date 1988

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0095-8956(88)90051-2

zbMATH Keywords

cubegraphlongest cycle

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38)

Review text

\textit{A. A. Evdokimov} [Maximal length of a circuit in a unitary n- dimensional cube, Mat. Zametki 6, 309-319 (1969; Zbl 0216.558)] has proved that the length of a longest cycle without chords in the graph of d-cube is greater than \(c2^ d\), where c is a positive constant. A recurrence inequality is derived which yields a short and simple proof of this result.

Recommendations

• scientific article; zbMATH DE number 6519645
• The snake-in-the-box problem: A new upper bound
• An upper bound on the size of the snake-in-the-box
• A backward search algorithm for the snake in the box problem
• On the solvability of domino snake problems
• Remarks on the box problem
• Sloane's box stacking problem

Cites work

• A Method for Constructing Circuit Codes
• A new upper bound for the length of snakes
• scientific article; zbMATH DE number 3503304 (Why is no real title available?)
• scientific article; zbMATH DE number 3503305 (Why is no real title available?)
• scientific article; zbMATH DE number 3564855 (Why is no real title available?)
• scientific article; zbMATH DE number 3368649 (Why is no real title available?)
• Lengths of snakes in boxes
• Upper bounds on the length of circuits of even spread in the d-cube

Cited in

(15)

• A new lower bound for snake-in-the-box codes
• Further results on snakes in powers of complete graphs
• Covering the hypercube with a bounded number of disjoint snakes
• On constructing snakes in powers of complete graphs
• Separator-based graph embedding into multidimensional grids with small edge-congestion
• Snakes, coils, and single-track circuit codes with spread \(k\)
• An algorithm for a problem of the largest induced cycles in Q^n
• scientific article; zbMATH DE number 6519645 (Why is no real title available?)
• On the snake-in-the-box codes for rank modulation under Kendall's \(\tau \)-metric
• The Complexity of Snake
• Hypercube sandwich approach to conferencing.
• Long induced paths in expanders
• Reconfigurable routing in data center networks
• The leaf function of Penrose P2 graphs
• On the length of longest chordless cycles

This page was built for publication: On the snake in the box problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1113920)