# King's graph

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

King's graph $8\times 8$ king's graph
Vertices$nm$ Edges$4nm-3(n+m)+2$ Girth$3$ when $\min(m,n)>1$ Chromatic number$4$ when $\min(m,n)>1$ Chromatic index$8$ when $\min(m,n)>2$ Table of graphs and parameters

For an $n\times m$ king's graph the total number of vertices is $nm$ and the number of edges is $4nm-3(n+m)+2$ . For a square $n\times n$ king's graph this simplifies so that the total number of vertices is $n^{2}$ and the total number of edges is $(2n-2)(2n-1)$ .

The neighbourhood of a vertex in the king's graph corresponds to the Moore neighborhood for cellular automata. 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.