knight's graph

{{Short description|Mathematical graph relating to chess}}

{{infobox graph

| name = Knight's graph

| image = 180px

| image_caption = $8\backslash times\; 8$ knight's graph

| vertices = $mn$

| edges = $4mn-6(m+n)+8$ (if $n\backslash ge\; 2$ and $m\backslash ge\; 2$)

| chromatic_number =

| chromatic_index =

| girth = 4 (if $n\backslash ge\; 3$ and $m\backslash ge\; 5$)

| properties = bipartite

}}

In graph theory, a knight's graph, or a knight's tour graph, is a graph that represents all legal moves of the knight chess piece on a chessboard. Each vertex of this graph represents a square of the chessboard, and each edge connects two squares that are a knight's move apart from each other.

More specifically, an $m\; \backslash times\; n$ knight's graph is a knight's graph of an $m\; \backslash times\; n$ chessboard.{{citation|title=Problem Solving Through Recreational Mathematics|title-link=Problem Solving Through Recreational Mathematics|first1=Bonnie|last1=Averbach|author1-link=Bonnie Averbach|first2=Orin|last2=Chein|publisher=Dover|year=1980|isbn=9780486131740|page=[https://books.google.com/books?id=xRJxJ7L9sq8C&pg=PA195 195]}}.

Its vertices can be represented as the points of the Euclidean plane whose Cartesian coordinates $(x,y)$ are integers with $1\backslash le\; x\backslash le\; m$ and $1\backslash le\; y\backslash le\; n$ (the points at the centers of the chessboard squares), and with two

vertices connected by an edge when their Euclidean distance is $\backslash sqrt\{5\}$.

For an $m\; \backslash times\; n$ knight's graph, the number of vertices is $nm$. If $m>1$ and $n>1$ then the number of edges is $4mn-6(m+n)+8$ (otherwise there are no edges). For an $n\; \backslash times\; n$ knight's graph, these simplify so that the number of vertices is $n^2$ and the number of edges is $4(n-2)(n-1)$.{{Cite OEIS|A033996}}

A Hamiltonian cycle on the knight's graph is a (closed) knight's tour. A chessboard with an odd number of squares has no tour, because the knight's graph is a bipartite graph (each color of squares can be used as one of two independent sets, and knight moves always change square color) and only bipartite graphs with an even number of vertices can have Hamiltonian cycles. Most chessboards with an even number of squares have a knight's tour; Schwenk's theorem provides an exact listing of which ones do and which do not.{{citation|title=Across the Board: The Mathematics of Chessboard Problems. Paradoxes, perplexities, and mathematical conundrums for the serious head scratcher|first=John J.|last=Watkins|publisher=Princeton University Press|year=2004|isbn=978-0-691-15498-5|pages=44, 68|url=https://books.google.com/books?id=EQSPm1MPKJUC&pg=PA44}}.

When it is modified to have toroidal boundary conditions (meaning that a knight is not blocked by the edge of the board, but instead continues onto the opposite edge) the $4\backslash times\; 4$ knight's graph is the same as the four-dimensional hypercube graph.