Knight's graph

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.

Uses your system voice; voice and rate in settings.

Snapshot

≈ 5 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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 \times n knight's graph is a knight's graph of an m \times n chessboard. Its vertices can be represented as the points of the Euclidean plane whose Cartesian coordinates (x,y) are integers with 1\le x\le m and 1\le y\le n (the points at the centers of the chessboard squares), and with two vertices connected by an edge when their Euclidean distance is \sqrt{5} .

For an m \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 \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) .

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.…

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 \times n knight's graph is a knight's graph of an m \times n chessboard. Its vertices can be represented as the points of the Euclidean plane whose Cartesian coordinates (x,y) are integers with 1\le x\le m and 1\le y\le n (the points at the centers of the chessboard squares), and with two vertices connected by an edge when their Euclidean distance is \sqrt{5} .

For an m \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 \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) .

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. 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\times 4 knight's graph is the same as the four-dimensional hypercube graph.

See also

King's graph Queen's graph Rook's graph Bishop's graph Lattice graph

Text derived from https://en.wikipedia.org/w/index.php?oldid=1347242793 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.