# Knight's graph

infobox graph

name = Knight's graph

image_caption = 8x8 Knight's graph

vertices = "nm"

edges = 4"mn"-6("m"+"n")+8

chromatic_number =

chromatic_index =

girth = 4 (if "n"≥3, "m"≥ 5)

properties = Ingraph theory , a**knight's tour graph**is a graph that represents all legal moves of the knightchess piece on achessboard where each vertex represents a square on a chessboard and each edge is a legal move.More specifically, an $n\; imes\; m$ knight's tour graph is a knight's tour graph of an $n\; imes\; m$ chessboard.For a $n\; imes\; m$ knight's tour graph the total number of vertices is simply "nm".

For a $n\; imes\; n$ knight's tour graph the total number of vertices is simply "n

^{2}" and the total number of edges is "4(n–2)(n–1)".Additionally, the number of edges for various "n" is identified as OEIS2C|id=A033996 in theOn-Line Encyclopedia of Integer Sequences .A

Hamiltonian path on the knight's tour graph is aknight's tour The following Knight's graph shows the number of possible moves that can be made from each position on an 8×8 chessboard.

**ee also***

Knight's tour

*King's graph

*Rook's graph

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Knight's tour**— The Knight s Tour is a mathematical problem involving a knight on a chessboard. The knight is placed on the empty board and, moving according to the rules of chess, must visit each square exactly once. olutionsThere are a great many solutions to… … Wikipedia**Graph theory**— In mathematics and computer science, graph theory is the study of graphs : mathematical structures used to model pairwise relations between objects from a certain collection. A graph in this context refers to a collection of vertices or nodes and … Wikipedia**graph theory**— Math. the branch of mathematics dealing with linear graphs. [1965 70] * * * Mathematical theory of networks. A graph consists of nodes (also called points or vertices) and edges (lines) connecting certain pairs of nodes. An edge that connects a… … Universalium**Knight (chess)**— The knight (unicode|♘ unicode|♞, sometimes referred to by players as a horse ) is a piece in the game of chess, representing a knight (armoured cavalry). It is normally represented by a horse s head.Each player starts with two knights, which… … Wikipedia**Rook's graph**— infobox graph name = Rook s graph image caption = 8x8 Rook s graph vertices = nm edges = nm ( n + m )/2 nm diameter = 2 chromatic number = max( n , m ) chromatic index = girth = 3 (if max( n , m ) ≥ 3) properties = regular, vertex transitive,… … Wikipedia**King's graph**— infobox graph name = King s graph image caption = 8x8 King s graph vertices = nm edges = 4 nm 3( n + m )+2 chromatic number = chromatic index = girth = properties = In graph theory, a king s graph is a graph that represents all legal moves of the … Wikipedia**Scene graph**— A scene graph is a general data structure commonly used by vector based graphics editing applications and modern computer games. Examples of such programs include AutoCAD, Adobe Illustrator, Acrobat 3D, OpenSceneGraph and CorelDRAW.The scene… … Wikipedia**List of graph theory topics**— This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 … Wikipedia**Hamiltonian path**— This article is about the overall graph theory concept of a Hamiltonian path. For the specific problem of determining whether a Hamiltonian path or cycle exists in a given graph, see Hamiltonian path problem. A Hamiltonian cycle in a dodecahedron … Wikipedia**List of mathematics articles (K)**— NOTOC K K approximation of k hitting set K ary tree K core K edge connected graph K equivalence K factor error K finite K function K homology K means algorithm K medoids K minimum spanning tree K Poincaré algebra K Poincaré group K set (geometry) … Wikipedia