Laceable Knight Graphs
Requires a Wolfram Notebook System
Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.
This Demonstration shows how to get from any white square on a chessboard to any black square by a sequence of knight moves that visits all squares. Such a route is called a Hamiltonian path, as opposed to a Hamiltonian cycle, which starts and finishes on the same square. Drag the two locators to change the start and finish squares.
Contributed by: Stan Wagon (July 2012)
(Macalester College)
Open content licensed under CC BY-NC-SA
Snapshots
Details
Let denote the knight graph: knight moves on an board, where is always assumed. The graph is always bipartite. A bipartite graph having the property that one can get from any point in one part to any point in the other part using a Hamiltonian path is called Hamilton-laceable. This Demonstration shows that is Hamilton-laceable, thus extending the very old result that is Hamiltonian.
By a theorem of A. Schwenk [1], the collection of graphs that admit Hamiltonian cycles consists of with and even; with odd, , and even; and with even and . Of these, I have shown that the following are not laceable: , , , , and , while the following are laceable: , , , , , and . Thus, one conjecture is that the Hamiltonian graph is laceable iff .
Reference
[1] A. Schwenk, "Which Rectangular Chessboards Have a Knight’s Tour?," Mathematics Magazine, 64(5), 1991 pp. 325–332. www.jstor.org/stable/2690649.
Permanent Citation