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 \times 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.

Rights

URN

URN:NBN:SI:DOC-V2Z5F9ZG

COBISSID

17584985

Added

29.05.2020

Metadata

Citation

APA:

Dupuis, Michael, Wagon, Stan (2015). Laceable knights. Ars mathematica contemporanea, volume 9, issue 1, str. 115-124. URN:NBN:SI:DOC-V2Z5F9ZG from http://www.dlib.si

MLA:

Dupuis, Michael, Wagon, Stan. "Laceable knights." Ars mathematica contemporanea volume 9. issue 1 (2015) str. 115-124.
<http://www.dlib.si/?URN=URN:NBN:SI:DOC-V2Z5F9ZG>

Ars mathematica contemporanea
2008-
(Assembly record)