King's graph

King's graph
8x8 King's graph
Vertices	nm
Edges	4nm-3(n+m)+2

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

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