A bipartite graph is Hamilton-laceable if for any two vertices in different parts there is a Hamiltonian path from one to the other. Using two main ideas (an algorithm for finding Hamiltonian paths and a decomposition lemma to move from smaller cases to larger) we show that the graph of knight’s moves on an m × n board is Hamilton-laceable iff m ≥ 6, n ≥ 6, and one of m, n is even. We show how the algorithm leads to new conjectures about Hamiltonian paths for various families, such as generalized Petersen graphs, I-graphs, and cubic symmetric graphs.
@article{420,
title = {Laceable knights},
journal = {ARS MATHEMATICA CONTEMPORANEA},
volume = {9},
year = {2014},
doi = {10.26493/1855-3974.420.3c5},
language = {EN},
url = {http://dml.mathdoc.fr/item/420}
}
Dupuis, Michael; Wagon, Stan. Laceable knights. ARS MATHEMATICA CONTEMPORANEA, Tome 9 (2014) . doi : 10.26493/1855-3974.420.3c5. http://gdmltest.u-ga.fr/item/420/