View source for Queen's graph

{{Short description|Mathematical graph relating to chess}}
{{infobox graph
 | name = Queen's graph
 | image = 
{{Chess diagram  
| center
|
|  |  |  |oo|  |  |  |oo
|oo|  |  |oo|  |  |oo|  
|  |oo|  |oo|  |oo|  |  
|  |  |oo|oo|oo|  |  |  
|oo|oo|oo|ql|oo|oo|oo|oo
|  |  |oo|oo|oo|  |  |  
|  |oo|  |oo|  |oo|  |  
|oo|  |  |oo|  |  |oo|  
}}
 | image_caption = In an <math>8\times 8</math> queen's [[graph (discrete mathematics)|graph]], each square of the chessboard above is a [[vertex (graph theory)|vertex]]. There is an edge between any two vertices that a queen could move between; as an example, the vertices [[adjacency (graph theory)|adjacent]] to d4 are marked with a white dot (i.e. there is an [[edge (graph theory)|edge]] from d4 to each marked vertex).
 | vertices = <math>mn</math>
 | edges = 
 | chromatic_number = ''n'' if <math>m=n\equiv 1,5 \pmod 6</math>
 | chromatic_index = 
 | girth = 
 | properties = [[Biconnected graph|Biconnected]], [[Hamiltonian cycle|Hamiltonian]]
}}
In mathematics, a '''queen's graph''' is an [[undirected graph]] that represents all legal moves of the [[queen (chess)|queen]]—a [[chess piece]]—on a [[chessboard]]. In the graph, each [[vertex (graph theory)|vertex]] represents a square on a chessboard, and each [[edge (graph theory)|edge]] is a legal move the queen can make, that is, a horizontal, vertical or diagonal move by any number of squares. If the chessboard has dimensions <math>m\times n</math>, then the induced graph is called the <math>m\times n</math> queen's graph.

[[Independent set (graph theory)|Independent set]]s of the graphs correspond to placements of multiple queens where no two queens are attacking each other. They are studied in the [[eight queens puzzle]], where eight non-attacking queens are placed on a standard <math>8\times 8</math> chessboard. [[Dominating set]]s represent arrangements of queens where every square is attacked or occupied by a queen; five queens, but no fewer, can dominate the <math>8\times 8</math> chessboard.

[[Graph coloring|Colourings]] of the graphs represent ways to colour each square so that a queen cannot move between any two squares of the same colour; at least ''n'' colours are needed for an <math>n\times n</math> chessboard, but 9 colours are needed for the <math>8\times 8</math> board.

==Properties==
<!-- Edges are the union of a rook's graph and bishop's graph edges? -->
There is a [[Hamiltonian cycle]] for each queen's graph, and the graphs are [[biconnected graph|biconnected]] (they remain [[connectivity (graph theory)|connected]] if any single vertex is removed). The special cases of the <math>1\times n</math> and <math>2\times 2</math> queen's graphs are [[complete graph|complete]].<ref name="MathWorld">{{mathworld|title=Queen Graph|urlname=QueenGraph}}</ref>

==Independence==
{{Chess diagram small
| tright
|
|__|__|ql|__|__|__|__|__
|__|__|__|__|ql|__|__|__
|__|ql|__|__|__|__|__|__
|__|__|__|__|__|__|__|ql
|ql|__|__|__|__|__|__|__
|__|__|__|__|__|__|ql|__
|__|__|__|ql|__|__|__|__
|__|__|__|__|__|ql|__|__
| An independent set of size 8 for an <math>8\times 8</math> chessboard (such sets are necessarily also dominating).<ref name="Averbach"/>
}}
{{Main|Eight queens puzzle}}
An [[independent set (graph theory)|independent set]] of the graph corresponds to a placement of several queens on a chessboard such that no two queens are attacking each other. In an <math>n\times n</math> chessboard, the largest independent set contains at most ''n'' vertices, as no two queens can be in the same row or column.<ref name="Averbach">{{cite book|title=Problem Solving Through Recreational Mathematics|title-link=Problem Solving Through Recreational Mathematics|last1=Averbach|first1=Bonnie|author1-link=Bonnie Averbach|last2=Chein|first2=Orin|publisher=[[Dover Publications]]|year=2000|isbn=9780486131740|pages=211–212}}</ref> This upper bound can be achieved for all ''n'' except ''n''=2 and ''n''=3.<ref>{{cite journal |last=Bernhardsson |first=Bo |date=1991 |title=Explicit Solutions to the N-Queens Problem for All N |journal=ACM Sigart |volume=2 |issue=2 |pages=7 |doi=10.1145/122319.122322|s2cid=10644706}}</ref> In the case of n=8, this is the traditional eight queens puzzle.<ref name="Averbach"/>

==Domination==
A [[dominating set]] of the queen's graph corresponds to a placement of queens such that every square on the chessboard is either attacked or occupied by a queen. On an <math>8\times 8</math> chessboard, five queens can dominate, and this is the minimum number possible<ref name="Watkins" />{{rp|113–114}} (four queens leave at least two squares unattacked). There are 4,860 such placements of five queens, including ones where the queens control also all occupied squares, i.e. they attack respectively protect each other. In this subgroup, there are also positions where the queens occupy squares on the main diagonal only<ref name="Watkins"/>{{rp|113–114}} (e.g. from a1 to h8), or all on a subdiagonal (e.g. from a2 to g8).<ref>[https://www.researchgate.net/figure/Dominating-sets-of-queens-on-a-standard-chessboard_fig3_35457519 Dominating queens - in researchgate.net]</ref><ref>[https://www.pleacher.com/mp/puzzles/miscpuz3/mobquen5.html 5 Queens on a Chessboard]</ref>
{|
| style="vertical-align:top" |{{Chess diagram small
| tright
|
|__|__|__|__|__|__|__|__
|__|__|__|__|__|__|__|__
|__|__|__|__|__|ql|__|__
|__|__|ql|__|__|__|__|__
|__|__|__|__|ql|__|__|__
|__|__|__|__|__|__|ql|__
|__|__|__|ql|__|__|__|__
|__|__|__|__|__|__|__|__
| A dominating (and independent) set of size 5.
}}
|
| style="vertical-align:top" |{{Chess diagram small
| tright
|
|__|__|__|__|__|__|__|__
|__|__|__|__|__|__|ql|__
|__|__|__|__|__|ql|__|__
|__|__|__|__|ql|__|__|__
|__|__|__|__|__|__|__|__
|__|__|ql|__|__|__|__|__
|__|__|__|__|__|__|__|__
|ql|__|__|__|__|__|__|__
| A dominating set on the main diagonal.
}}
|
| style="vertical-align:top" |{{Chess diagram small
| tright
|
|__|__|__|__|__|__|ql|__
|__|__|__|__|__|__|__|__
|__|__|__|__|ql|__|__|__
|__|__|__|ql|__|__|__|__
|__|__|ql|__|__|__|__|__
|__|__|__|__|__|__|__|__
|ql|__|__|__|__|__|__|__
|__|__|__|__|__|__|__|__
| A dominating set on a sub diagonal.
}}
|}
Modifying the graph by replacing the non-looping rectangular <math>8\times 8</math> chessboard with a [[torus]] or [[cylinder]] reduces the minimum dominating set size to four.<ref name="Watkins">{{cite book|title=Across the Board: The Mathematics of Chessboard Problems|last=Watkins|first=John J.|year=2012|publisher=[[Princeton University Press]]}}</ref>{{rp|139}}

{{Chess diagram 5x5
| tright
|
|xo|__|xo|__|xo
|__|xo|xo|xo|__
|xo|xo|xx|xo|xo
|__|xo|xo|xo|__
|xo|__|xo|__|xo
| Dotted squares are adjacent to the centre square. The 8 non-adjacent squares are adjacent in the corresponding [[knight's graph]].<ref name="Watkins"/>{{rp|117}}
}}
The <math>3\times 3</math> queen's graph is dominated by the single vertex at the centre of the board. The centre vertex of the <math>5\times 5</math> queen's graph is [[adjacency (graph theory)|adjacent]] to all but 8 vertices: those vertices that are adjacent to the centre vertex of the <math>5\times 5</math> [[knight's graph]].<ref name="Watkins"/>{{rp|117}}

===Domination numbers===
Define the domination number ''d''(''n'') of an <math>n\times n</math> queen's graph to be the size of the smallest dominating set, and the diagonal domination number ''dd''(''n'') to be the size of the smallest dominating set that is a subset of the long diagonal. Note that <math>d(n)\le dd(n)</math> for all ''n''. The bound is attained for <math>d(8)=dd(8)=5</math>, but not for <math>d(11)=5,dd(11)=7</math>.<ref name="Watkins"/>{{rp|119}}

The domination number is linear in ''n'', with bounds given by:<ref name="Watkins"/>{{rp|119, 121}}
: <math>\frac{n-1}{2} \le d(n)\le n-\left \lfloor \frac{n}{3}\right \rfloor.</math>

Initial values of ''d''(''n''), for <math>n=1,2,3,\dots</math>, are 1, 1, 1, 2, 3, 3, 4, 5, 5, 5, 5 {{OEIS|id=A075458}}.

Let ''K<sub>n</sub>'' be the maximum size of a subset of <math>\{1,2,3,\dots,n\}</math> such that every number has the same [[parity (mathematics)|parity]] and no three numbers form an [[arithmetic progression]] (the set is "midpoint-free"). The diagonal domination number of an <math>n\times n</math> queen's graph is <math>n-K_n</math>.<ref name="Watkins"/>{{rp|116}}

Define the independent domination number ''ID''(''n'') to be the size of the smallest independent, dominant set in an <math>n\times n</math> queen's graph. It is known that <math>ID(n)<0.705n+0.895</math>.<ref>{{cite journal|title=Chessboard domination problems|journal=[[Discrete Mathematics (journal)|Discrete Mathematics]]|last=Cockayne|first=E. J.|volume=86|issue=1–3|year=1990|pages=13–20|doi=10.1016/0012-365X(90)90344-H|doi-access=free|hdl=1828/2415|hdl-access=free}}</ref>

==Colouring==
[[File:Queen's graph colouring.jpg|thumb|alt=Refer to caption|A 9-[[graph coloring|colouring]] of the <math>8\times 8</math> queen's graph.<ref>{{cite journal|title=On Coloring the <math>n\times n</math> Chessboard|journal=[[The American Mathematical Monthly]]|last1=Iyer|first1=M. R.|last2=Menon|first2=V. V.|volume=72|issue=7|year=1966|page=723}}</ref> Notice that each pair of squares with the same colour are not on the same rank, file or diagonal, so a queen could not move directly between the squares.]]

A [[graph coloring|colouring]] of the queen's graph is an assignment of colours to each vertex such that no two adjacent vertices are given the same colour. For instance, if a8 is coloured red then no other square on the a-[[file (chess)|file]], eighth [[rank (chess)|rank]] or long diagonal can be coloured red, as a queen can move from a8 to any of these squares. The chromatic number of the graph is the smallest number of colours that can be used to colour it.

In the case of an <math>n\times n</math> queen's graph, at least ''n'' colours are required, as each square in a rank or file needs a different colour (i.e. the rows and columns are [[clique (graph theory)|cliques]]).<ref name="MathWorld"/> The chromatic number is exactly ''n'' if <math>n\equiv 1,5 \pmod 6</math> (i.e. ''n'' is one more or one less than a multiple of 6).<ref>{{cite web|url=http://users.encs.concordia.ca/~chvatal/queengraphs.html|title=Colouring the queen graphs|last=Chvátal|first=Václav|author-link=Václav Chvátal|accessdate=14 February 2022}}</ref>

The chromatic number of an <math>8\times 8</math> queen's graph is 9.<ref>{{cite journal|title=A survey of known results and research areas for ''n''-queens|journal=[[Discrete Mathematics (journal)|Discrete Mathematics]]|last1=Bell|first1=Jordan|last2=Stevens|first2=Brett|volume=309|issue=1|year=2009|pages=1–31|doi=10.1016/j.disc.2007.12.043|doi-access=free}}</ref>

==Irredundance==
A set of vertices is irredundant if removing any vertex from the set changes the [[neighbourhood (graph theory)|neighbourhood]] of the set i.e. for each vertex, there is an adjacent vertex that is not adjacent to any other vertex in the set. This corresponds to a set of queens which each uniquely control at least one square. The maximum size ''IR''(''n'') of an irredundant set on the <math>n\times n</math> queen's graph is difficult to characterise; known values include <math>IR(5)=5,IR(6)=7,IR(7)=9,IR(8)=11.</math><ref name="Watkins"/>{{rp|206–207}}

==Pursuit–evasion game==
Consider the [[pursuit–evasion]] game on an <math>8\times 8</math> queen's graph played according to the following rules: a white queen starts in one corner and a black queen in the opposite corner. Players alternate moves, which consist of moving the queen to an adjacent vertex that can be reached without passing over (horizontally, vertically or diagonally) or landing on a vertex that is adjacent to the opposite queen. This game can be won by white with a [[pairing strategy]].{{sfn|Averbach|Chein|2000|pages=257–258, 443}}

==See also==
* [[King's graph]]
* [[Knight's graph]]
* [[Rook's graph]]
* [[Bishop's graph]]
* {{portal-inline|Chess}}

==References==
{{reflist}}

[[Category:Mathematical chess problems]]
[[Category:Parametric families of graphs]]