Laceable Knight Graphs

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.

THINGS TO TRY

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

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.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.