Knight's graph

From Wikipedia, the free encyclopedia

Knight's graph

8x8 Knight's graph
Vertices nm
Edges 4mn-6(m+n)+8
This box: view • talk • edit

In graph theory, a knight's tour graph is a graph that represents all legal moves of the knight piece on a chessboard where each vertex represents a square on a chessboard and each edge is a legal move. More specifically, an n \times m knight's tour graph is a knight's tour graph of an n \times m chessboard.

For a n \times m knight's tour graph the total number of vertices is simply nm.

For a n \times n knight's tour graph the total number of vertices is simply n2 and the total number of edges is 4(n − 2)(n − 1). Additionally, the number of edges for various n is identified as A033996 in the On-Line Encyclopedia of Integer Sequences.

A Hamiltonian path on the knight's tour graph is a knight's tour

[edit] See also

 This chess-related article is a stub. You can help Wikipedia by expanding it.