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).