Laceable knights - Dupuis, Michael (Ars mathematica contemporanea, 2015)
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 \ge 6$?, ?$n \ge 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.
Keywords: generalized Petersen graphs; graf skakačevih skokov; Hamilton-connected; Hamiltonian paths; Hamilton-laceable; Hamiltonove poti; hamiltonsko-povezan; hamiltonsko-premostljiv; knight graph; posplošeni Petersenovi grafi; sledljiv; traceable