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
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)
|
(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)
| |||
|
(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 left panel shows a detail of a woodcut from Vinciolo's lace pattern book (Vinciolo 1603, p. 23 recto). The middle panel shows the corresponding grid reconstructed by Guillochon (2026b). Each mesh
is represented by a vertex, and two vertices
are adjacent when their meshes share a side
or corner. The open meshes determine an induced subgraph
of the king graph. Its connected components
are the regions connected through side or corner contacts. Guillochon's counting
model requires invariance under all eight symmetries
of the square and excludes isolated
vertices in the selected induced subgraph.
These restrictions describe the counting model, rather than a general definition
of lace. For
, 2, ..., the numbers of such selections, including
the empty set, are 1, 2, 6, 7, 48, 55, 705, 861, 21454,
26696, ... (OEIS A402110).
The count generalizes to patterns in which every connected component of the induced subgraph has at
least vertices.
The smallest such component in the 19 reconstructed symmetric panels had five meshes.
It is the central cross highlighted in the middle panel. The right panel shows the
induced subgraph on these five vertices.
The gallery shows the 19 reconstructed panels from 13 pages of Vinciolo's book (Guillochon 2026ab). The woodcut shows the upper design on page 31 recto (Vinciolo 1603, p. 31 recto). In the adjacent reconstruction, the eight highlighted regions are connected components of nine open meshes each. The eight symmetries of the square carry any one of these components to all eight positions.
The king graph contains the Möbius
ladder
as a subgraph for
and so is not unit-distance.