King's graph

---

title: "King's graph" type: doc version: 1 created: 2026-02-28 author: "Wikipedia contributors" status: active scope: public tags: ["mathematical-chess-problems", "parametric-families-of-graphs"] description: "Graph of king moves on a chessboard" topic_path: "general/mathematical-chess-problems" source: "https://en.wikipedia.org/wiki/King's_graph" license: "CC BY-SA 4.0" wikipedia_page_id: 0 wikipedia_revision_id: 0

::summary Graph of king moves on a chessboard ::

::data[format=table title="infobox graph"]

Field	Value
name	King's graph
image	King's graph with white king.svg
image_caption	8\times 8 king's graph
vertices	nm
edges	4nm-3(n+m)+2
chromatic_number	4 when \min(m,n)1
chromatic_index	8 when \min(m,n)2
girth	3 when \min(m,n)1
::

| name = King's graph | image = King's graph with white king.svg | image_caption = 8\times 8 king's graph | vertices = nm | edges = 4nm-3(n+m)+2 | chromatic_number = 4 when \min(m,n)1 | chromatic_index = 8 when \min(m,n)2 | girth = 3 when \min(m,n)1 | properties = In graph theory, a king's graph is a graph that represents all legal moves of the king chess piece on a chessboard where each vertex represents a square on a chessboard and each edge is a legal move. More specifically, an n \times m king's graph is a king's graph of an n \times m chessboard.{{citation | last = Chang | first = Gerard J. | editor1-last = Du | editor1-first = Ding-Zhu | editor2-last = Pardalos | editor2-first = Panos M. | contribution = Algorithmic aspects of domination in graphs | location = Boston, MA | mr = 1665419 | pages = 339–405 | publisher = Kluwer Acad. Publ. | title = Handbook of combinatorial optimization, Vol. 3 | year = 1998}}. Chang defines the king's graph on p. 341. It is the map graph formed from the squares of a chessboard by making a vertex for each square and an edge for each two squares that share an edge or a corner. It can also be constructed as the strong product of two path graphs.{{citation | last1 = Berend | first1 = Daniel | last2 = Korach | first2 = Ephraim | last3 = Zucker | first3 = Shira | contribution = Two-anticoloring of planar and related graphs | contribution-url = http://www.emis.de/journals/DMTCS/pdfpapers/dmAD0130.pdf | location = Nancy | mr = 2193130 | pages = 335–341 | publisher = Association for Discrete Mathematics & Theoretical Computer Science | series = Discrete Mathematics & Theoretical Computer Science Proceedings | title = 2005 International Conference on Analysis of Algorithms | year = 2005}}.

For an n \times m king's graph the total number of vertices is n m and the number of edges is 4nm -3(n + m) + 2. For a square n \times n king's graph this simplifies so that the total number of vertices is n^2 and the total number of edges is (2n-2)(2n-1).

The neighbourhood of a vertex in the king's graph corresponds to the Moore neighborhood for cellular automata.{{citation | last = Smith | first = Alvy Ray | authorlink = Alvy Ray Smith | contribution = Two-dimensional formal languages and pattern recognition by cellular automata | doi = 10.1109/SWAT.1971.29 | pages = 144–152 | title = 12th Annual Symposium on Switching and Automata Theory | year = 1971}}. A generalization of the king's graph, called a kinggraph, is formed from a squaregraph (a planar graph in which each bounded face is a quadrilateral and each interior vertex has at least four neighbors) by adding the two diagonals of every quadrilateral face of the squaregraph.{{citation |last1 = Chepoi |first1 = Victor |last2 = Dragan |first2 = Feodor |last3 = Vaxès |first3 = Yann |contribution = Center and diameter problems in plane triangulations and quadrangulations |pages = 346–355 |isbn = 0-89871-513-X |title = Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '02) |year = 2002 |url = https://archive.org/details/proceedingsofthi2002acms/page/346 |citeseerx = 10.1.1.1.7694

In the drawing of a king's graph obtained from an n\times m chessboard, there are (n-1)(m-1) crossings, but it is possible to obtain a drawing with fewer crossings by connecting the two nearest neighbors of each corner square by a curve outside the chessboard instead of by a diagonal line segment. In this way, (n-1)(m-1)-4 crossings are always possible. For the king's graph of small chessboards, other drawings lead to even fewer crossings; in particular every 2\times n king's graph is a planar graph. However, when both n and m are at least four, and they are not both equal to four, (n-1)(m-1)-4 is the optimal number of crossings.{{citation | last1 = Klešč | first1 = Marián | last2 = Petrillová | first2 = Jana | last3 = Valo | first3 = Matúš | issue = 1 | journal = Carpathian Journal of Mathematics | jstor = 43999517 | mr = 3099062 | pages = 27–32 | title = Minimal number of crossings in strong product of paths | volume = 29 | year = 2013| doi = 10.37193/CJM.2013.01.13 | doi-access = free | last = Ma | first = Dengju | journal = The Australasian Journal of Combinatorics | mr = 3631655 | pages = 35–47 | title = The crossing number of the strong product of two paths | url = https://ajc.maths.uq.edu.au/pdf/68/ajc_v68_p035.pdf | volume = 68 | year = 2017}}

References

References

1. {{Cite OEIS. A002943

::callout[type=info title="Wikipedia Source"] This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page. ::