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. 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](https://txtdot.deep-swarm.xyz/proxy/img?url=https%3A%2F%2Fmathworld.wolfram.com%2Fimages%2Fequations%2FKingGraph%2FInline4.svg){kind=small}
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 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
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).
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.
See also
Bishop Graph, Black Bishop Graph, Knight Graph, Rook Graph, Triangular Honeycomb King Graph, White Bishop Graph
Explore with Wolfram|Alpha
References
Karavaev, A. M. "FlowProblem: Statistics of Simple Cycles." http://flowproblem.ru/paths/statistics-of-simple-cycles.Mertens, S. "Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph." 15 Aug 2024. https://arxiv.org/abs/2408.08053.Perepechko, S. N. and Voropaev, A. N. "The Number of Fixed Length Cycles in an Undirected Graph. Explicit Formulae in Case of Small Lengths."Sloane, N. J. A. Sequences A002943, A140521, and A158651 in "The On-Line Encyclopedia of Integer Sequences."
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "King Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/KingGraph.html