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 strong graph
product
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
(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).
Mertens (2024) computed the domination polynomial and numbers of dominating sets for king graphs up to
.