Queen's graph
Queen's graph | |||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
In an queen's edge from d4 to each marked vertex). | |||||||||||||||||||||||||||||||||||||||||||||
Vertices | |||||||||||||||||||||||||||||||||||||||||||||
Chromatic number | n if | ||||||||||||||||||||||||||||||||||||||||||||
Properties | Hamiltonian | ||||||||||||||||||||||||||||||||||||||||||||
Table of graphs and parameters |
In mathematics, a queen's graph is an
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 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 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 chessboard, but 9 colours are needed for the board.
Properties
There is a
Independence
a | b | c | d | e | f | g | h | ||
8 | ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() | 8 | |||||||
7 | 7 | ||||||||
6 | 6 | ||||||||
5 | 5 | ||||||||
4 | 4 | ||||||||
3 | 3 | ||||||||
2 | 2 | ||||||||
1 | 1 | ||||||||
a | b | c | d | e | f | g | h |
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 chessboard, the largest independent set contains at most n vertices, as no two queens can be in the same row or column.[2] This upper bound can be achieved for all n except n=2 and n=3.[3] In the case of n=8, this is the traditional eight queens puzzle.[2]
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 chessboard, five queens can dominate, and this is the minimum number possible[4]: 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[4]: 113–114 (e.g. from a1 to h8), or all on a subdiagonal (e.g. from a2 to g8).[5][6]
A dominating (and independent) set of size 5.
|
A dominating set on the main diagonal.
|
A dominating set on a sub diagonal.
|
Modifying the graph by replacing the non-looping rectangular chessboard with a torus or cylinder reduces the minimum dominating set size to four.[4]: 139
![]() | ![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() | ![]() |
![]() | ![]() | ![]() | ![]() | ![]() |
The queen's graph is dominated by the single vertex at the centre of the board. The centre vertex of the queen's graph is
Domination numbers
Define the domination number d(n) of an 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 for all n. The bound is attained for , but not for .[4]: 119
The domination number is linear in n, with bounds given by:[4]: 119, 121
Initial values of d(n), for , 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 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 queen's graph is .[4]: 116
Define the independent domination number ID(n) to be the size of the smallest independent, dominant set in an queen's graph. It is known that .[7]
Colouring
![Refer to caption](http://upload.wikimedia.org/wikipedia/commons/thumb/0/03/Queen%27s_graph_colouring.jpg/220px-Queen%27s_graph_colouring.jpg)
A
In the case of an 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).[1] The chromatic number is exactly n if (i.e. n is one more or one less than a multiple of 6).[9]
The chromatic number of an queen's graph is 9.[10]
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 queen's graph is difficult to characterise; known values include [4]: 206–207
Pursuit–evasion game
Consider the pursuit–evasion game on an 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.[11]
See also
References
- ^ a b Weisstein, Eric W. "Queen Graph". MathWorld.
- ^ ISBN 9780486131740.
- S2CID 10644706.
- ^ a b c d e f g h i Watkins, John J. (2012). Across the Board: The Mathematics of Chessboard Problems. Princeton University Press.
- ^ Dominating queens - in researchgate.net
- ^ 5 Queens on a Chessboard
- hdl:1828/2415.
- ^ Iyer, M. R.; Menon, V. V. (1966). "On Coloring the Chessboard". The American Mathematical Monthly. 72 (7): 723.
- ^ Chvátal, Václav. "Colouring the queen graphs". Retrieved 14 February 2022.
- .
- ^ Averbach & Chein 2000, pp. 257–258, 443.