Hamiltonian Paths and Knight's Tours

I encountered Hamiltonian paths before but never in the context of my daily number count. The reason is clear when we look at Figure 1 showing the initial members of OEIS A003216:

A003216

Number of Hamiltonian graphs with \(n\) nodes.

Figure 1: source

Looking at Figure 1, it can be seen that \(n\)=8 yields a value of 6196 but \(n\)=9 yields a value of 177083. This is a massive jump that completely misses the numbers that I am traversing as I track my diurnal age. Currently I am 26241 days old and one of the properties of this number is that it is a member of OEIS A283420 where \(n\)=9:

A283420

Number of simple (not necessarily connected) untraceable graphs on \(n\) nodes.

Even in the A283420 sequence the numbers get large very quickly. Here are the values from \(n\)=1 to 11: 0, 1, 2, 6, 16, 65, 310, 2316, 26241, 522596, 18766354. My current diurnal age just happened to be a member of this sequence and this is what led me to reacquaint myself with Hamiltonian graphs. Figure 2 shows all the possible non-Hamiltonian graphs for the case of \(n\)=5:

Figure 2: source

Looking at Figure 2, the distinction between graphs that are connected and those that are disconnected is apparent. But what about the terms simple and untraceable? At this point, it's a good idea to define separately what is meant by a simple graph and traceable graph (which will then explain an untraceable graph).

To quote from WolframMath World:

A simple graph, also called a strict graph, is an unweighted, undirected graph containing no graph loops or multiple edges. A simple graph may be either connected or disconnected. Figure 3 shows the differences between a simple graph and a nonsimple one:

Figure 3: source

A traceable graph is a graph that possesses a Hamiltonian path. Hamiltonian graphs are therefore traceable, but the converse is not necessarily true. The numbers of traceable graphs on \(n\)=1, 2, ... are 1, 1, 2, 5, 18, 91, 734, ... (OEIS A057864), where the singleton graph \(K_1\) is conventionally considered traceable. The first few are illustrated in Figure 4, with a Hamiltonian path indicated in orange for each. Source.

Figure 4: source

Comparing Figures 2 and 4, it can be seen what it is that defines a Hamiltonian path and a Hamiltonian cycle:

A Hamiltonian path or traceable path is a path that visits each vertex of the graph exactly once. A graph that contains a Hamiltonian path is called a traceable graph ... A Hamiltonian cycle, Hamiltonian circuit, vertex tour or graph cycle is a cycle that visits each vertex exactly once. A graph that contains a Hamiltonian cycle is called a Hamiltonian graph. Source.

Figure 5 shows a Hamiltonian cycle for the dodecahedron. 

Figure 5: source

A knight's tour can be viewed as either a Hamiltonian cycle or path when each square is regarded as a vertex:

A knight's tour is a sequence of moves of a knight on a chessboard such that the knight visits every square exactly once. If the knight ends on a square that is one knight's move from the beginning square (so that it could tour the board again immediately, following the same path), the tour is closed; otherwise, it is open. The knight's tour problem is an instance of the more general Hamiltonian path problem in graph theory. The problem of finding a closed knight's tour is similarly an instance of the Hamiltonian cycle problem. Unlike the general Hamiltonian path problem, the knight's tour problem can be solved in linear time. Source.

Figure 6 shows an open knight's tour that is a Hamiltonian path but not a cycle:

Figure 6: source

It has been shown that closed knight's tours are possible on any \(m\) x \(n\) board with \(m\) ≤ \(n\) unless one or more of these three conditions are met:

• \(m\) and \(n\) are both odd
• \(m\) = 1, 2, or 4
• \(m\) = 3 and \(n\) = 4, 6, or 8

On an 8 × 8 board, there are exactly 26,534,728,821,064 directed closed tours (i.e. two tours along the same path that travel in opposite directions are counted separately, as are rotations and reflections). The number of undirected closed tours is half this number, since every tour can be traced in reverse. Source. 

Finally let's not fail to mention the great mathematician, Sir William Rowan Hamilton, after whom the Hamiltonian paths and cycles were named. Figure 7 shows a photograph of him.

Figure 7: Hamilton (1805-1865)

For a brief account of his life, follow this link.