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.

Independent sets of the graphs correspond to placements of multiple queens where no two queens are attacking each other.

There is a Hamiltonian cycle for each queen's graph, and the graphs are biconnected (they remain connected if any single vertex is removed).

[1] 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.

chessboard, the largest independent set contains at most n vertices, as no two queens can be in the same row or column.

[3] In the case of n=8, this is the traditional eight queens puzzle.

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] Modifying the graph by replacing the non-looping rectangular

chessboard with a torus or cylinder reduces the minimum dominating set size to four.

queen's graph is dominated by the single vertex at the centre of the board.

queen's graph is adjacent to all but 8 vertices: those vertices that are adjacent to the centre vertex of the

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.

[4]: 119 The domination number is linear in n, with bounds given by:[4]: 119, 121 Initial values of d(n), for

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").

[4]: 116 Define the independent domination number ID(n) to be the size of the smallest independent, dominant set in an

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.

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).

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

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.