The king graph is a graph with vertices in which each vertex represents a square in an chessboard, and each edge corresponds to a legal move by a king.
The number of edges in the king graph is , so for , 2, ..., the first few values are 0, 6, 20, 42, 72, 110, ... (OEIS A002943).
The order graph has chromatic number for and for . For , 3, ..., the edge chromatic numbers are 3, 8, 8, 8, 8, ....
King graphs are implemented in the Wolfram Language as GraphData["King", m, n].
All king graphs are Hamiltonian and biconnected. The only regular king graph is the -king graph, which is isomorphic to the tetrahedral graph . The -king graphs are planar only for (with the case corresponding to path graphs) and , some embeddings of which are illustrated above.
The -king graph is perfect iff (S. Wagon, pers. comm., Feb. 22, 2013).
Closed formulas for the numbers of -cycles of with are given by
(1)
| |||
(2)
| |||
(3)
| |||
(4)
|
where the formula for appears in Perepechko and Voropaev.
The numbers of Hamiltonian cycles for the -king graphs for , 3, ... are 6, 32, 5660, 4924128, ... (OEIS A140521), with the corresponding numbers of Hamiltonian paths given by 24, 784, 343184, ... (OEIS A158651).