Queen's graph
Mathematical graph relating to chess / From Wikipedia, the free encyclopedia
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 , then the induced graph is called the queen's graph.
Queen's graph | |||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| |||||||||||||||||||||||||||||||||||||||||||||
Vertices | |||||||||||||||||||||||||||||||||||||||||||||
Chromatic number | n if | ||||||||||||||||||||||||||||||||||||||||||||
Properties | Biconnected, Hamiltonian | ||||||||||||||||||||||||||||||||||||||||||||
Table of graphs and parameters |
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.