King's graph
| King's graph | |
|---|---|
 [math]\displaystyle{ 8\times 8 }[/math] king's graph | |
| Vertices | [math]\displaystyle{ nm }[/math] |
| Edges | [math]\displaystyle{ 4nm-3(n+m)+2 }[/math] |
| Girth | [math]\displaystyle{ 3 }[/math] when [math]\displaystyle{ \min(m,n)\gt 1 }[/math] |
| Chromatic number | [math]\displaystyle{ 4 }[/math] when [math]\displaystyle{ \min(m,n)\gt 1 }[/math] |
| Chromatic index | [math]\displaystyle{ 8 }[/math] when [math]\displaystyle{ \min(m,n)\gt 2 }[/math] |
| 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 [math]\displaystyle{ n \times m }[/math] king's graph is a king's graph of an [math]\displaystyle{ n \times m }[/math] 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 [math]\displaystyle{ n \times m }[/math] king's graph the total number of vertices is [math]\displaystyle{ n m }[/math] and the number of edges is [math]\displaystyle{ 4nm -3(n + m) + 2 }[/math]. For a square [math]\displaystyle{ n \times n }[/math] king's graph this simplifies so that the total number of vertices is [math]\displaystyle{ n^2 }[/math] and the total number of edges is [math]\displaystyle{ (2n-2)(2n-1) }[/math].[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 [math]\displaystyle{ n\times m }[/math] chessboard, there are [math]\displaystyle{ (n-1)(m-1) }[/math] 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, [math]\displaystyle{ (n-1)(m-1)-4 }[/math] crossings are always possible. For the king's graph of small chessboards, other drawings lead to even fewer crossings; in particular every [math]\displaystyle{ 2\times n }[/math] king's graph is a planar graph. However, when both [math]\displaystyle{ n }[/math] and [math]\displaystyle{ m }[/math] are at least four, and they are not both equal to four, [math]\displaystyle{ (n-1)(m-1)-4 }[/math] is the optimal number of crossings.[6][7]
See also
References
- ↑ Chang, Gerard J. (1998), "Algorithmic aspects of domination in graphs", in Du, Ding-Zhu; Pardalos, Panos M., Handbook of combinatorial optimization, Vol. 3, Boston, MA: Kluwer Acad. Publ., pp. 339–405. Chang defines the king's graph on p. 341.
- ↑ Berend, Daniel; Korach, Ephraim; Zucker, Shira (2005), "Two-anticoloring of planar and related graphs", 2005 International Conference on Analysis of Algorithms, Discrete Mathematics & Theoretical Computer Science Proceedings, Nancy: Association for Discrete Mathematics & Theoretical Computer Science, pp. 335–341, http://www.emis.de/journals/DMTCS/pdfpapers/dmAD0130.pdf.
- ↑ Sloane, N. J. A., ed. "Sequence A002943". OEIS Foundation. https://oeis.org/A002943.
- ↑ "Two-dimensional formal languages and pattern recognition by cellular automata", 12th Annual Symposium on Switching and Automata Theory, 1971, 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, ISBN 0-89871-513-X, https://archive.org/details/proceedingsofthi2002acms/page/346.
- ↑ 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
- ↑ Ma, Dengju (2017), "The crossing number of the strong product of two paths", The Australasian Journal of Combinatorics 68: 35–47, https://ajc.maths.uq.edu.au/pdf/68/ajc_v68_p035.pdf
 |  |
