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 =
In graph theory, 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 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 "n2" 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 the On-Line Encyclopedia of Integer Sequences.

A Hamiltonian path on the knight's tour graph is a knight'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

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.