TOPICS
Search

King Graph


KingGraphsChessboard

The m×n king graph, for positive integers m and n, is a graph with mn vertices in which each graph vertex represents a square in an m×n 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 of two path graphs.

KingsGraph

n×n king graphs abstracted from the chessboard are illustrated above for n=2, ..., 6. The 1×1 king graph is the singleton graph K_1 and the 2×2 king graph is isomorphic to the tetrahedral graph K_4.

The number of edges in the n×n king graph is 2(n-1)(2n-1), so for n=1, 2, ..., the first few values are 0, 6, 20, 42, 72, 110, ... (OEIS A002943).

The n×n king graph has chromatic number gamma=1 for n=1 and gamma=4 for n>=2. For n=2, 3, ..., the edge chromatic numbers are 3, 8, 8, 8, 8, ....

King graphs are implemented in the Wolfram Language as GraphData[{"King", {m, n}}].

KingGraphPlanar

King graphs with m,n>=2 are Hamiltonian and biconnected. The only regular king graph with m,n>=2 is the (2,2)-king graph, which is isomorphic to the tetrahedral graph K_4. The (m,n)-king graphs are planar only for min(m,n)=1,2 (with the min(m,n)=1 case corresponding to path graphs) and (m,n)=(3,3), some graph embeddings of which are illustrated above.

For positive integers 1<=m<=n, the graph crossing number of the m×n 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.
(1)

The (m,n)-king graph is perfect iff min(m,n)<=3 (S. Wagon, pers. comm., Feb. 22, 2013).

The numbers c_k of k-cycles of the n×n king graph satisfy the following formulas, valid for n>=2 for c_3, c_4, and c_5, and for n>=3 for c_6:

c_3=4(n-1)^2
(2)
c_4=12(n-1)^2-10(n-1)+1
(3)
c_5=4(n-2)(9n-14)
(4)
c_6=2[63(n-2)^2-15(n-2)-7],
(5)

where c_6=0 for n=2. The formula for c_5 appears in Voropaev and Perepechko.

The numbers of directed Hamiltonian cycles for the (n,n)-king graphs for n=2, 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 n×n king graphs up to n=22.

KingGraphVincioloLace

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 61×61 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 n=1, 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 k 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.

KingGraphVincioloGallery

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 n×n king graph contains the Möbius ladder M_6 as a subgraph for n>=4 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

Guillochon, J. "A New Sequence: Vinciolo's Lace." SeqFan. Nov. 9, 2026a. https://groups.google.com/g/seqfan/c/4hbZq_2eAhQ/m/KsB6u220AQAJ.Guillochon, J. "Vinciolo's Lace." Nov. 2026b. https://guillochon.github.io/vinciolo-lace/.House of Graphs. King Graphs. Singleton Graph, Tetrahedron K4, 3x3 King's Graph, 4x4 King Graph, and others.Karavaev, A. M. "FlowProblem: Statistics of Simple Cycles." https://web.archive.org/web/20161015201528/http://flowproblem.ru/cycles/statistics-of-simple-cycles.Klešč, M.; Petrillová, J.; and Valo, M. "Minimal Number of Crossings in Strong Product of Paths." Carpathian J. Math. 29, 27-32, 2013. https://doi.org/10.37193/CJM.2013.01.13.Ma, D. "The Crossing Number of the Strong Product of Two Paths." Australas. J. Combin. 68, 35-47, 2017. https://ajc.maths.uq.edu.au/pdf/68/ajc_v68_p035.pdf.Mertens, S. "Domination Polynomials of the Grid, the Cylinder, the Torus, and the King Graph." 15 Aug 2024. https://arxiv.org/abs/2408.08053.Sloane, N. J. A. Sequences A002943, A140521, A158651, and A402110 in "The On-Line Encyclopedia of Integer Sequences."Voropaev, A. N. and Perepechko, S. N. "The Number of Fixed Length Cycles in an Undirected Graph: Explicit Formulae in Case of Small Lengths." Discrete Contin. Models Appl. Comput. Sci. No. 2, 6-12, 2012.Vinciolo, F. de. Les Secondes Oeuvres, et Subtiles Inventions De Lingerie du Seigneur Federic de Vinciolo Venitien. Paris, France: Jean Le Clerc, 1603. Pages 23 and 31 (recto), Metropolitan Museum of Art, 39.30(26) and 39.30(34). https://www.metmuseum.org/art/collection/search/662913. https://www.metmuseum.org/art/collection/search/662921.

Referenced on Wolfram|Alpha

King Graph

Cite this as:

Weisstein, Eric W. "King Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/KingGraph.html

Subject classifications