King's graph

King's graph
King's graph
	king's graph
Vertices
Edges
Girth	when
Chromatic number	when
Chromatic index	when
	Table of graphs and parameters

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.^[1] 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.^[2]

For an $n\times m$ king's graph the total number of vertices is $nm$ 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)$ .^[3]

The neighbourhood of a vertex in the king's graph corresponds to the Moore neighborhood for cellular automata.^[4] 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.^[5]

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.^[6]^[7]

References

^ Chang, Gerard J. (1998), "Algorithmic aspects of domination in graphs", in Du, Ding-Zhu; Pardalos, Panos M. (eds.), Handbook of combinatorial optimization, Vol. 3, Boston, MA: Kluwer Acad. Publ., pp. 339–405, MR 1665419. Chang defines the king's graph on p. 341.
^ Berend, Daniel; Korach, Ephraim; Zucker, Shira (2005), "Two-anticoloring of planar and related graphs" (PDF), 2005 International Conference on Analysis of Algorithms, Discrete Mathematics & Theoretical Computer Science Proceedings, Nancy: Association for Discrete Mathematics & Theoretical Computer Science, pp. 335–341, MR 2193130.
^ Sloane, N. J. A. (ed.). "Sequence A002943". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
^ Smith, Alvy Ray (1971), "Two-dimensional formal languages and pattern recognition by cellular automata", 12th Annual Symposium on Switching and Automata Theory, pp. 144–152, doi:10.1109/SWAT.1971.29.
^ Chepoi, Victor; Dragan, Feodor; Vaxès, Yann (2002), "Center and diameter problems in plane triangulations and quadrangulations", Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '02), pp. 346–355, CiteSeerX 10.1.1.1.7694, ISBN 0-89871-513-X.
^ Klešč, Marián; Petrillová, Jana; Valo, Matúš (2013), "Minimal number of crossings in strong product of paths", Carpathian Journal of Mathematics, 29 (1): 27–32, doi:10.37193/CJM.2013.01.13, JSTOR 43999517, MR 3099062
^ Ma, Dengju (2017), "The crossing number of the strong product of two paths" (PDF), The Australasian Journal of Combinatorics, 68: 35–47, MR 3631655

[1] Chang, Gerard J. (1998), "Algorithmic aspects of domination in graphs", in Du, Ding-Zhu; Pardalos, Panos M. (eds.), Handbook of combinatorial optimization, Vol. 3, Boston, MA: Kluwer Acad. Publ., pp. 339–405, MR 1665419. Chang defines the king's graph on p. 341.

[2] Berend, Daniel; Korach, Ephraim; Zucker, Shira (2005), "Two-anticoloring of planar and related graphs" (PDF), 2005 International Conference on Analysis of Algorithms, Discrete Mathematics & Theoretical Computer Science Proceedings, Nancy: Association for Discrete Mathematics & Theoretical Computer Science, pp. 335–341, MR 2193130.

[3] Sloane, N. J. A. (ed.). "Sequence A002943". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

[4] Smith, Alvy Ray (1971), "Two-dimensional formal languages and pattern recognition by cellular automata", 12th Annual Symposium on Switching and Automata Theory, pp. 144–152, doi:10.1109/SWAT.1971.29.

[5] Chepoi, Victor; Dragan, Feodor; Vaxès, Yann (2002), "Center and diameter problems in plane triangulations and quadrangulations", Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '02), pp. 346–355, CiteSeerX 10.1.1.1.7694, ISBN 0-89871-513-X.

[6] Klešč, Marián; Petrillová, Jana; Valo, Matúš (2013), "Minimal number of crossings in strong product of paths", Carpathian Journal of Mathematics, 29 (1): 27–32, doi:10.37193/CJM.2013.01.13, JSTOR 43999517, MR 3099062

[7] Ma, Dengju (2017), "The crossing number of the strong product of two paths" (PDF), The Australasian Journal of Combinatorics, 68: 35–47, MR 3631655

[1]

[2]

[3]

[4]

[5]

[6]

[7]

See also

References