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 king's graph is a king's graph of an 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.
For an king's graph the total number of vertices is and the number of edges is. For a square king's graph, the total number of vertices is and the total number of edges is.
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 by adding the two diagonals of every quadrilateral face of the squaregraph.
