|
| |
|
|
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
|
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.]
|
|
|
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
|
|
|
|
KEYWORD
|
nonn,more
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
