|
%I #18 Oct 21 2017 09:45:18
%S 10,16,22,46,56,92,106,138,172,212,254
%N a(n) is the smallest N such that the {n,n+1}-leaper graph with 2n+1 rows and N columns has a Hamiltonian cycle.
%C An {r,s}-leaper graph is a chessboard-like graph, with two vertices adjacent when an {r,s}-leaper can leap from one to the other. When r=1 and s=2 we have an ordinary knight's move; in general, an {r,s}-leaper goes from (x,y) to (x +- r, y +- s) or to (x +- s, y +- r). The theory of these graphs is developed in the paper ``Leaper Graphs'', which discusses the values of a(1) through a(7) and gives a quadratic lower bound.
%C This problem turns out to be an excellent benchmark for the special case of TSP solvers where the intercity distances are just 0 and infinity.
%C The values of a(2) and a(3) are due to George Jelliss; I found a(4) and a(5); and Michael Juenger found a(6) and a(7).
%C Michael Juenger has found that A152138(10)=212 and A152138(11)=254. As noted earlier, this means that he should be credited for establishing the values of a(6) thru a(11) in this sequence. (Added Jun 24 2010)
%H George Jelliss, <a href="http://www.mayhematics.com/t/t.htm">Knight's Tour Notes</a> [Added by _N. J. A. Sloane_, Oct 01 2009]
%H George Jelliss, <a href="/A152138/a152138.gif">Knight's Tours on 3 X 10 board</a> [An illustration from the web page Knight's Tour Notes] [Added by _N. J. A. Sloane_, Oct 01 2009]
%H George Jelliss, <a href="http://www.ktn.freeuk.com/cc.htm">Chronology of Knight's Tours</a> [Added by _N. J. A. Sloane_, Oct 01 2009]
%H D. E. Knuth, <a href="https://arxiv.org/abs/math/9411240">Leaper Graphs</a>, arXiv:math/9411240 [math.CO], 1994; The Mathematical Gazette, 78 (1994), 274-297. [To be reprinted in a 2010 book, Selected Papers on Fun and Games.]
%H Mario Velucchi, <a href="http://www.velucchi.it/mathchess/knight.htm">Knight's Tours</a> [Added by _N. J. A. Sloane_, Oct 01 2009]
%e We have a(1)=10 because a 3 X 10 chessboard was shown to be Hamiltonian by Bergholt in 1918, while there clearly are no Hamiltonian cycles on a 3 X 8 or 3 X 6 or 3 X 4 or 3 X 2 or 3 X odd.
%K nonn,more
%O 1,1
%A _Don Knuth_, Sep 30 2009, Jun 24 2010
| 