King's graph
Graph of king moves on a chessboard From Wikipedia, the free encyclopedia
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 king's graph is a king's graph of an chessboard.[1] It is the map graph formed from the squares of a chessboard by making a vertex for each square and an edge for each two squares that share an edge or a corner. It can also be constructed as the strong product of two path graphs.[2]
King's graph | |
---|---|
![]() king's graph | |
Vertices | |
Edges | |
Girth | when |
Chromatic number | when |
Chromatic index | when |
Table of graphs and parameters |
For an king's graph the total number of vertices is and the number of edges is . For a square king's graph this simplifies so that the total number of vertices is and the total number of edges is .[3]
The neighbourhood of a vertex in the king's graph corresponds to the Moore neighborhood for cellular automata.[4] A generalization of the king's graph, called a kinggraph, is formed from a squaregraph (a planar graph in which each bounded face is a quadrilateral and each interior vertex has at least four neighbors) by adding the two diagonals of every quadrilateral face of the squaregraph.[5]
In the drawing of a king's graph obtained from an chessboard, there are crossings, but it is possible to obtain a drawing with fewer crossings by connecting the two nearest neighbors of each corner square by a curve outside the chessboard instead of by a diagonal line segment. In this way, crossings are always possible. For the king's graph of small chessboards, other drawings lead to even fewer crossings; in particular every king's graph is a planar graph. However, when both and are at least four, and they are not both equal to four, is the optimal number of crossings.[6][7]
See also
References
Wikiwand - on
Seamless Wikipedia browsing. On steroids.