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)
|
 |  | ![2[63(n-2)^2-15(n-2)-7],](/images/equations/KingGraph/Inline40.svg) |
(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).
