King's graph

{{Short description|Graph of king moves on a chessboard}}

{{infobox graph

| name = King's graph

| image = King's graph with white king.svg

| image_caption = $8\backslash times\; 8$ king's graph

| vertices = $nm$

| edges = $4nm-3(n+m)+2$

| chromatic_number = $4$ when $\backslash min(m,n)>1$

| chromatic_index = $8$ when $\backslash min(m,n)>2$

| girth = $3$ when $\backslash min(m,n)>1$

| properties =

}}

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\; \backslash times\; m$ king's graph is a king's graph of an $n\; \backslash times\; m$ chessboard.{{citation

| last = Chang | first = Gerard J.

| editor1-last = Du | editor1-first = Ding-Zhu

| editor2-last = Pardalos | editor2-first = Panos M.

| contribution = Algorithmic aspects of domination in graphs

| location = Boston, MA

| mr = 1665419

| pages = 339–405

| publisher = Kluwer Acad. Publ.

| title = Handbook of combinatorial optimization, Vol. 3

| year = 1998}}. Chang defines the king's graph on [https://books.google.com/books?id=w0rmms0_hMMC&pg=PA341 p. 341]. 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.{{citation

| last1 = Berend | first1 = Daniel

| last2 = Korach | first2 = Ephraim

| last3 = Zucker | first3 = Shira

| contribution = Two-anticoloring of planar and related graphs

| contribution-url = http://www.emis.de/journals/DMTCS/pdfpapers/dmAD0130.pdf

| location = Nancy

| mr = 2193130

| pages = 335–341

| publisher = Association for Discrete Mathematics & Theoretical Computer Science

| series = Discrete Mathematics & Theoretical Computer Science Proceedings

| title = 2005 International Conference on Analysis of Algorithms

| year = 2005}}.

For an $n\; \backslash times\; m$ king's graph the total number of vertices is $n\; m$ and the number of edges is $4nm\; -3(n\; +\; m)\; +\; 2$. For a square $n\; \backslash 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)$.{{Cite OEIS|A002943}}

The neighbourhood of a vertex in the king's graph corresponds to the Moore neighborhood for cellular automata.{{citation

| last = Smith | first = Alvy Ray | authorlink = Alvy Ray Smith

| contribution = Two-dimensional formal languages and pattern recognition by cellular automata

| doi = 10.1109/SWAT.1971.29

| pages = 144–152

| title = 12th Annual Symposium on Switching and Automata Theory

| year = 1971}}.

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.{{citation |last1 = Chepoi

|first1 = Victor

|last2 = Dragan

|first2 = Feodor

|last3 = Vaxès

|first3 = Yann

|contribution = Center and diameter problems in plane triangulations and quadrangulations

|pages = [https://archive.org/details/proceedingsofthi2002acms/page/346 346–355]

|isbn = 0-89871-513-X

|title = Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '02)

|year = 2002

|url = https://archive.org/details/proceedingsofthi2002acms/page/346

|citeseerx = 10.1.1.1.7694

}}.

In the drawing of a king's graph obtained from an $n\backslash 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\backslash 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.{{citation

| last1 = Klešč | first1 = Marián

| last2 = Petrillová | first2 = Jana

| last3 = Valo | first3 = Matúš

| issue = 1

| journal = Carpathian Journal of Mathematics

| jstor = 43999517

| mr = 3099062

| pages = 27–32

| title = Minimal number of crossings in strong product of paths

| volume = 29

| year = 2013| doi = 10.37193/CJM.2013.01.13

| doi-access = free

}}{{citation

| last = Ma | first = Dengju

| journal = The Australasian Journal of Combinatorics

| mr = 3631655

| pages = 35–47

| title = The crossing number of the strong product of two paths

| url = https://ajc.maths.uq.edu.au/pdf/68/ajc_v68_p035.pdf

| volume = 68

| year = 2017}}