Laceable Knight Graphs

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram CDF Player or other Wolfram Language products.

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

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.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send