King's graph

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 king 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 king's graph is a king's graph of an n imes m chessboard.

For a n imes m king's graph the total number of vertices is simply n m.

For a n imes n king's graph the total number of vertices is simply n^2 and the total number of edges is (2n-2)(2n-1).Additionally, the number of edges for various n is identified as OEIS2C|id=A002943 in the On-Line Encyclopedia of Integer Sequences.

ee also

* Knight's graph
* Rook's graph


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • King (chess) — In chess, the King (unicode|♔, unicode|♚) is the most important piece. The object of the game is to trap the opponent s king so that it would not be able to avoid capture (checkmate). If a player s king is threatened with capture, it is said to… …   Wikipedia

  • King Kong vs. Godzilla — Original theatrical poster Directed by Ishirō Honda Produced by Tomoyuki Tanaka …   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

  • 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… …   Wikipedia

  • Cubic graph — Not to be confused with graphs of cubic functions. The Petersen graph is a Cubic graph …   Wikipedia

  • Dyck graph — The Dyck graph Named after W. Dyck Vertices 32 Edges …   Wikipedia

  • Molecular graph — In chemical graph theory and in mathematical chemistry, a molecular graph or chemical graph is a representation of the structural formula of a chemical compound in terms of graph theory. A chemical graph is a labeled graph whose vertices… …   Wikipedia

  • List of The King of Fighters characters — The cast of characters of King of Fighters XI. The King of Fighters fighting game series, produced by SNK Playmore, includes a wide cast of characters, some of which are taken from other SNK games. The story takes place in a fictional universe in …   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

  • Moore neighborhood — The Moore neighborhood comprises eight cells which surround center C. In cellular automata, the Moore neighborhood comprises the eight cells surrounding a central cell on a two dimensional square lattice. The neighborhood is named after Edward F …   Wikipedia

Share the article and excerpts

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