Jump to content

King's graph

From Wikipedia, the free encyclopedia
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 king's graph is a king's graph of an 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 king's graph the total number of vertices is and the number of edges is . For a square king's graph this simplifies so that the total number of vertices is and the total number of edges is .[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 chessboard, there are 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, crossings are always possible. For the king's graph of small chessboards, other drawings lead to even fewer crossings; in particular every king's graph is a planar graph. However, when both and are at least four, and they are not both equal to four, is the optimal number of crossings.[6][7]

See also

[edit]

References

[edit]
  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