On the existence of Hamiltonian cycles in hypercubes

2024/09/04 by Di Pietro, Gabriele, Ripà, Marco
#05C12 #05C45 (Primary) 05C38 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2409.03073

Abstract

For each pair of positive integers (a,b) such that a ≥ 0 and b > 1, the present paper provides a necessary and sufficient condition for the existence of Hamiltonian cycles visiting all the vertices of any k-dimensional grid \0,1\^k ⊂ ℝ^k and whose associated Euclidean distance is equal to √(a²+b²). Our solution extends previously stated results in fairy chess on the existence of closed Euclidean (a,b)-leapers tours for 2 × 2 × ⋯ × 2 chessboards, where the (Euclidean) knight identifies the (1,2)-leaper.

Related

• Matchings in hypercubes extend to long cycles
• Matchings in Hypercubes Extend to Long Cycles
• The Second Leaper Theorem
• Saved by the rook: a case of matchings and Hamiltonian cycles
• Prescribed matchings extend to Hamiltonian cycles in hypercubes with faulty edges