The 
king graph, for positive
integers 
and 
, is a graph
with 
vertices
in which each graph vertex represents a square
in an 
chessboard,
and each graph edge corresponds to a legal move by
a king. It corresponds to the graph strong product ![P_m□AdjustmentBox[x, BoxMargins -> {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]P_n](/images/equations/KingGraph/Inline6.svg)
of two path graphs.
king graphs abstracted from the
chessboard are illustrated above for 
, ..., 6. The 
king graph is the singleton
graph 
and the 
king graph is isomorphic to the tetrahedral
graph 
.
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 
king 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
].
King graphs with 
are Hamiltonian and biconnected.
The only regular king graph with 
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 graph embeddings
of which are illustrated above.
For positive integers 
, the graph
crossing number of the 
king graph is given by (Klešč et al. 2013, Ma 2017)
![cr(P_m□AdjustmentBox[x, BoxMargins -> {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]P_n)={0 if m<=2; n-3 if m=3; 4 if m=n=4; (m-1)(n-1)-4 otherwise.](/images/equations/KingGraph/NumberedEquation1.svg) |
(1)
|
The 
-king graph is perfect iff 
(S. Wagon, pers. comm., Feb. 22, 2013).
The numbers 
of 
-cycles
of the 
king graph satisfy the following formulas, valid for 
for 
, 
,
and 
, and for 
for 
:
 |  |  |
(2)
|
 |  |  |
(3)
|
 |  |  |
(4)
|
 |  | ![2[63(n-2)^2-15(n-2)-7],](/images/equations/KingGraph/Inline58.svg) |
(5)
|
where 
for 
. The formula for 
appears in Voropaev and Perepechko.
The numbers of directed Hamiltonian cycles for the 
-king graphs for 
, 3, ... are 6, 32, 5660, 4924128, ... (OEIS A140521),
with the corresponding numbers of directed Hamiltonian
paths given by 24, 784, 343184, ... (OEIS A158651).
In both counts, the two opposite orientations are counted separately.
Mertens (2024) computed the domination polynomial and numbers of dominating sets for 
king graphs up to 
.
The 
king graph contains the Möbius
ladder 
as a subgraph for 
and so is not unit-distance.
