Metraipolis › archive › dc_72050b0dafa5

King's graph — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/King%27s_graph
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T17:25:31.616Z
SHA-256 of the archived text
e0dfee3a7cd14204f45d3bf278d31312daae230f3fa2088a426c5b108a7120f0
Stable URL of this page
https://metraipolis.com/documento/dc_72050b0dafa5

How to cite

King's graph — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/King%27s_graph (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_72050b0dafa5 (Metraipolis archive dc_72050b0dafa5, sha256 e0dfee3a7cd14204f45d3bf278d31312daae230f3fa2088a426c5b108a7120f0)
BibTeX
@misc{dc72050b0dafa5,
  title = {King's graph — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/King%27s_graph},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_72050b0dafa5; sha256 e0dfee3a7cd14204f45d3bf278d31312daae230f3fa2088a426c5b108a7120f0},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/King%27s_graph. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 × m {\displaystyle n\times m} king's graph is a king's graph of an n × m {\displaystyle n\times m} chessboard. 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. For an n × m {\displaystyle n\times m} king's graph the total number of vertices is n m {\displaystyle nm} and the number of edges is 4 n m − 3 ( n + m ) + 2 {\displaystyle 4nm-3(n+m)+2} . For a square n × n {\displaystyle n\times n} king's graph this simplifies so that the total number of vertices is n 2 {\displaystyle n^{2}} and the total number of edges is ( 2 n − 2 ) ( 2 n − 1 ) {\displaystyle (2n-2)(2n-1)} . The neighbourhood of a vertex in the king's graph corresponds to the Moore neighborhood for cellular automata. 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. In the drawing of a king's graph obtained from an n × m {\displaystyle n\times m} chessboard, there are ( n − 1 ) ( m − 1 ) {\displaystyle (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 {\displaystyle (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 × n {\displaystyle 2\times n} king's graph is a planar graph. However, when both n {\displaystyle n} and m {\displaystyle m} are at least four, and they are not both equal to four, ( n − 1 ) ( m − 1 ) − 4 {\displaystyle (n-1)(m-1)-4} is the optimal number of crossings.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «graph theory»).
Fonte: Wikipedia in inglese, voce «King's graph» — https://en.wikipedia.org/wiki/King%27s_graph
Wikidata Q6411145 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q6411145
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/King%27s_graph?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1369245674, consultata il 2026-10-07T16:56:50.769Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 5d6ef2052bb8cbb778bb3702bb928480f208245608d715939853b10e8fadfc6a