In graph theory, a rook's graph is an undirected graph that represents all legal moves of the rook chess piece on a chessboard. Each vertex of a rook's graph represents a square on a chessboard, and there is an edge between any two squares sharing a row (rank) or column (file), the squares that a rook can move between. These graphs can be constructed for chessboards of any rectangular shape. Although rook's graphs have only minor significance in chess lore, they are more important in the abstract mathematics of graphs through their alternative constructions: rook's graphs are the Cartesian product of two complete graphs, and are the line graphs of complete bipartite graphs. The square rook's graphs constitute the two-dimensional Hamming graphs. Rook's graphs are highly symmetric, having symmetries taking every vertex to every other vertex. In rook's graphs defined from square chessboards, more strongly, every two edges are symmetric, and every pair of vertices is symmetric to every other pair at the same distance in moves (making the graph distance-transitive). For rectangular chessboards whose width and height are relatively prime, the rook's graphs are circulant graphs. With one exception, the rook's graphs can be distinguished from all other graphs using only two properties: the numbers of triangles each edge belongs to, and the existence of a unique 4-cycle connecting each nonadjacent pair of vertices. Rook's graphs are perfect graphs. In other words, every subset of chessboard squares can be colored so that no two squares in a row or column have the same color, using a number of colors equal to the maximum number of squares from the subset in any single row or column (the clique number of the induced subgraph). This class of induced subgraphs are a key component of a decomposition of perfect graphs used to prove the strong perfect graph theorem, which characterizes all perfect graphs. The independence number and domination number of a rook's graph both equal the smaller of the chessboard's width and height. In terms of chess, the independence number is the maximum number of rooks that can be placed without attacking each other; the domination number is the minimum number needed to attack all unoccupied board squares. Rook's graphs are well-covered graphs, meaning that placing non-attacking rooks one at a time can never get stuck until a set of maximum size is reached.
Definition and mathematical constructions An n × m rook's graph represents the moves of a rook on an n × m chessboard. Its vertices represent the squares of the chessboard, and may be given coordinates (x, y), where 1 ≤ x ≤ n and 1 ≤ y ≤ m. Two vertices with coordinates (x1, y1) and (x2, y2) are adjacent if and only if either x1 = x2 or y1 = y2. (If x1 = x2, the vertices share a file and are connected by a vertical rook move; if y1 = y2, they share a rank and are connected by a horizontal rook move.) The squares of a single rank or file are all directly connected to each other, so each rank and file forms a clique—a subset of vertices forming a complete graph. The whole rook's graph for an n × m chessboard can be formed from these two kinds of cliques, as the Cartesian product of graphs Kn ◻ Km. Because the rook's graph for a square chessboard is the Cartesian product of equal-size cliques, it is an example of a Hamming graph. Its dimension as a Hamming graph is two, and every two-dimensional Hamming graph is a rook's graph for a square chessboard. Square rook's graphs are also called "Latin square graphs"; applied to a Latin square, its edges describe pairs of squares that cannot contain the same value. The Sudoku graphs are rook's graphs with some additional edges, connecting squares of a Sudoku puzzle that should have unequal values.
Geometrically, the rook's graphs can be formed by sets of the vertices and edges (the skeletons) of a family of convex polytopes, the Cartesian products of pairs of neighborly polytopes. For instance, the 3-3 duoprism is a four-dimensional shape formed as the Cartesian product of two triangles, and has a 3 × 3 rook's graph as its skeleton.
Regularity and symmetry
Strong regularity Moon (1963) and Hoffman (1964) observe that the m × n {\displaystyle m\times n} rook's graph (or equivalently, as they describe it, the line graph of the complete bipartite graph K m , n {\displaystyle K_{m,n}} ) has all of the following properties:
… excerpt ends here. Continue reading the full article.
