King's graph

From Wikipedia, the free encyclopedia

King's graph

8x8 King's graph
Vertices nm
Edges 4nm-3(n+m)+2
This box: view • talk • edit

In graph theory, a king's graph is a graph that represents all legal moves of the king 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.

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

For a n \times n king's graph the total number of vertices is simply n2 and the total number of edges is (2n − 2)(2n − 1). Additionally, the number of edges for various n is identified as A002943 in the On-Line Encyclopedia of Integer Sequences.

[edit] See also