King's graph

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
King's graph
King's graph with white king.svg
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 a king's graph the total number of vertices is and the number of edges is . For a square king's graph, 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]

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, ISBN 0-89871-513-X.