Misplaced Pages

Queen's graph

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
Mathematical graph relating to chess
Queen's graph
abcdefgh
8d8 white circleh8 white circlea7 white circled7 white circleg7 white circleb6 white circled6 white circlef6 white circlec5 white circled5 white circlee5 white circlea4 white circleb4 white circlec4 white circled4 white queene4 white circlef4 white circleg4 white circleh4 white circlec3 white circled3 white circlee3 white circleb2 white circled2 white circlef2 white circlea1 white circled1 white circleg1 white circle8
77
66
55
44
33
22
11
abcdefgh
In an 8 × 8 {\displaystyle 8\times 8} queen's graph, each square of the chessboard above is a vertex. There is an edge between any two vertices that a queen could move between; as an example, the vertices adjacent to d4 are marked with a white dot (i.e. there is an edge from d4 to each marked vertex).
Vertices m n {\displaystyle mn}
Chromatic numbern if m = n ≡ 1 , 5 ( mod 6 ) {\displaystyle m=n\equiv 1,5{\pmod {6}}}
PropertiesBiconnected, Hamiltonian
Table of graphs and parameters

In mathematics, a queen's graph is an undirected graph that represents all legal moves of the queen—a chess piece—on a chessboard. In the graph, each vertex represents a square on a chessboard, and each 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 m × n {\displaystyle m\times n} , then the induced graph is called the m × n {\displaystyle m\times n} queen's graph.

Independent sets 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 8 × 8 {\displaystyle 8\times 8} chessboard. Dominating sets represent arrangements of queens where every square is attacked or occupied by a queen; five queens, but no fewer, can dominate the 8 × 8 {\displaystyle 8\times 8} chessboard.

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 n × n {\displaystyle n\times n} chessboard, but 9 colours are needed for the 8 × 8 {\displaystyle 8\times 8} board.

Properties

There is a Hamiltonian cycle for each queen's graph, and the graphs are biconnected (they remain connected if any single vertex is removed). The special cases of the 1 × n {\displaystyle 1\times n} and 2 × 2 {\displaystyle 2\times 2} queen's graphs are complete.

Independence

abcdefgh
8c8 white queene7 white queenb6 white queenh5 white queena4 white queeng3 white queend2 white queenf1 white queen8
77
66
55
44
33
22
11
abcdefgh
An independent set of size 8 for an 8 × 8 {\displaystyle 8\times 8} chessboard (such sets are necessarily also dominating). Main article: Eight queens puzzle

An 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 n × n {\displaystyle n\times n} chessboard, the largest independent set contains at most n vertices, as no two queens can be in the same row or column. This upper bound can be achieved for all n except n=2 and n=3. In the case of n=8, this is the traditional eight queens puzzle.

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 8 × 8 {\displaystyle 8\times 8} chessboard, five queens can dominate, and this is the minimum number possible (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 (e.g. from a1 to h8), or all on a subdiagonal (e.g. from a2 to g8).

abcdefgh
8f6 white queenc5 white queene4 white queeng3 white queend2 white queen8
77
66
55
44
33
22
11
abcdefgh
A dominating (and independent) set of size 5.
abcdefgh
8g7 white queenf6 white queene5 white queenc3 white queena1 white queen8
77
66
55
44
33
22
11
abcdefgh
A dominating set on the main diagonal.
abcdefgh
8g8 white queene6 white queend5 white queenc4 white queena2 white queen8
77
66
55
44
33
22
11
abcdefgh
A dominating set on a sub diagonal.

Modifying the graph by replacing the non-looping rectangular 8 × 8 {\displaystyle 8\times 8} chessboard with a torus or cylinder reduces the minimum dominating set size to four.

a5 black circleb5c5 black circled5e5 black circle
a4b4 black circlec4 black circled4 black circlee4
a3 black circleb3 black circlec3 black crossd3 black circlee3 black circle
a2b2 black circlec2 black circled2 black circlee2
a1 black circleb1c1 black circled1e1 black circle
Dotted squares are adjacent to the centre square. The 8 non-adjacent squares are adjacent in the corresponding knight's graph.

The 3 × 3 {\displaystyle 3\times 3} queen's graph is dominated by the single vertex at the centre of the board. The centre vertex of the 5 × 5 {\displaystyle 5\times 5} queen's graph is adjacent to all but 8 vertices: those vertices that are adjacent to the centre vertex of the 5 × 5 {\displaystyle 5\times 5} knight's graph.

Domination numbers

Define the domination number d(n) of an n × n {\displaystyle n\times n} 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 d ( n ) ≤ d d ( n ) {\displaystyle d(n)\leq dd(n)} for all n. The bound is attained for d ( 8 ) = d d ( 8 ) = 5 {\displaystyle d(8)=dd(8)=5} , but not for d ( 11 ) = 5 , d d ( 11 ) = 7 {\displaystyle d(11)=5,dd(11)=7} .

The domination number is linear in n, with bounds given by:

n − 1 2 ≤ d ( n ) ≤ n − ⌊ n 3 ⌋ . {\displaystyle {\frac {n-1}{2}}\leq d(n)\leq n-\left\lfloor {\frac {n}{3}}\right\rfloor .}

Initial values of d(n), for n = 1 , 2 , 3 , … {\displaystyle n=1,2,3,\dots } , are 1, 1, 1, 2, 3, 3, 4, 5, 5, 5, 5 (sequence A075458 in the OEIS).

Let Kn be the maximum size of a subset of { 1 , 2 , 3 , … , n } {\displaystyle \{1,2,3,\dots ,n\}} such that every number has the same parity and no three numbers form an arithmetic progression (the set is "midpoint-free"). The diagonal domination number of an n × n {\displaystyle n\times n} queen's graph is n − K n {\displaystyle n-K_{n}} .

Define the independent domination number ID(n) to be the size of the smallest independent, dominant set in an n × n {\displaystyle n\times n} queen's graph. It is known that I D ( n ) < 0.705 n + 0.895 {\displaystyle ID(n)<0.705n+0.895} .

Colouring

Refer to caption
A 9-colouring of the 8 × 8 {\displaystyle 8\times 8} queen's graph. 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 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, eighth 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 n × n {\displaystyle n\times n} 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 cliques). The chromatic number is exactly n if n ≡ 1 , 5 ( mod 6 ) {\displaystyle n\equiv 1,5{\pmod {6}}} (i.e. n is one more or one less than a multiple of 6).

The chromatic number of an 8 × 8 {\displaystyle 8\times 8} queen's graph is 9.

Irredundance

A set of vertices is irredundant if removing any vertex from the set changes the 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 n × n {\displaystyle n\times n} queen's graph is difficult to characterise; known values include I R ( 5 ) = 5 , I R ( 6 ) = 7 , I R ( 7 ) = 9 , I R ( 8 ) = 11. {\displaystyle IR(5)=5,IR(6)=7,IR(7)=9,IR(8)=11.}

Pursuit–evasion game

Consider the pursuit–evasion game on an 8 × 8 {\displaystyle 8\times 8} 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.

See also

References

  1. ^ Weisstein, Eric W. "Queen Graph". MathWorld.
  2. ^ Averbach, Bonnie; Chein, Orin (2000). Problem Solving Through Recreational Mathematics. Dover Publications. pp. 211–212. ISBN 9780486131740.
  3. Bernhardsson, Bo (1991). "Explicit Solutions to the N-Queens Problem for All N". ACM Sigart. 2 (2): 7. doi:10.1145/122319.122322. S2CID 10644706.
  4. ^ Watkins, John J. (2012). Across the Board: The Mathematics of Chessboard Problems. Princeton University Press.
  5. Dominating queens - in researchgate.net
  6. 5 Queens on a Chessboard
  7. Cockayne, E. J. (1990). "Chessboard domination problems". Discrete Mathematics. 86 (1–3): 13–20. doi:10.1016/0012-365X(90)90344-H. hdl:1828/2415.
  8. Iyer, M. R.; Menon, V. V. (1966). "On Coloring the n × n {\displaystyle n\times n} Chessboard". The American Mathematical Monthly. 72 (7): 723.
  9. Chvátal, Václav. "Colouring the queen graphs". Retrieved 14 February 2022.
  10. Bell, Jordan; Stevens, Brett (2009). "A survey of known results and research areas for n-queens". Discrete Mathematics. 309 (1): 1–31. doi:10.1016/j.disc.2007.12.043.
  11. Averbach & Chein 2000, pp. 257–258, 443.
Categories: