login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 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.

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), 274-297. [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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 27 21:12 EDT 2020. Contains 334671 sequences. (Running on oeis4.)