

A152138


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.


1



10, 16, 22, 46, 56, 92, 106, 138, 172, 212, 254
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

An {r,s}leaper graph is a chessboardlike 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.
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.
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).
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)


LINKS

Table of n, a(n) for n=1..11.
George Jelliss, Knight's Tour Notes [Added by N. J. A. Sloane, Oct 01 2009]
George Jelliss, Knight's Tours on 3 X 10 board [An illustration from the web page Knight's Tour Notes] [Added by N. J. A. Sloane, Oct 01 2009]
George Jelliss, Chronology of Knight's Tours [Added by N. J. A. Sloane, Oct 01 2009]
D. E. Knuth, Leaper Graphs, arXiv:math/9411240 [math.CO], 1994; The Mathematical Gazette, 78 (1994), 274297. [To be reprinted in a 2010 book, Selected Papers on Fun and Games.]
Mario Velucchi, Knight's Tours [Added by N. J. A. Sloane, Oct 01 2009]


EXAMPLE

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.


CROSSREFS

Sequence in context: A136799 A055987 A187397 * A109100 A155151 A104788
Adjacent sequences: A152135 A152136 A152137 * A152139 A152140 A152141


KEYWORD

nonn,more


AUTHOR

Don Knuth, Sep 30 2009, Jun 24 2010


STATUS

approved



