Knight's graph
From Infogalactic: the planetary knowledge core
Knight's graph | |
---|---|
180px
8x8 Knight's graph
|
|
Vertices | nm |
Edges | 4mn-6(m+n)+8 |
Girth | 4 (if n≥3, m≥ 5) |
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 where each vertex represents a square on a chessboard and each edge is a legal move. More specifically, an knight's tour graph is a knight's tour graph of an chessboard.[1]
For a knight's tour graph the total number of vertices is simply . For a knight's tour graph the total number of vertices is simply and the total number of edges is .[2]
A Hamiltonian path on the knight's tour graph is a knight's tour.[1] Schwenk's theorem characterizes the sizes of chessboard for which a knight's tour exist.[3]
References
- ↑ 1.0 1.1 Lua error in package.lua at line 80: module 'strict' not found..
- ↑ "Sloane's A033996 ", The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
- ↑ Lua error in package.lua at line 80: module 'strict' not found..