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 each edge connects two squares on the same row (rank) or on the same column (file) as each other, the squares that a rook can move between. These graphs can be constructed for chessboards of any rectangular shape, and can be defined mathematically as the Cartesian product of two complete graphs, as the two-dimensional Hamming graphs, or as the line graphs of complete bipartite 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 (thus, they are distance-transitive). For rectangular chessboards whose two side lengths are relatively prime to each other, the rook's graphs are circulant graphs. With one exception, the rook's graphs can be distinguished from all other graphs by the numbers of triangles each edge belongs to and by the existence of a -cycle connecting each nonadjacent pair of vertices. Rook's graphs are perfect graphs, meaning that every subset of chessboard squares can be colored so that no two squares in a row or column have the same color, and so that the number of colors equals the maximum number of squares from the subset in any single row or column (the clique number of an induced subgraph). The graphs formed in this way from subsets of squares in a rook's graph form one of the key components of a decomposition of perfect graphs used to prove the strong perfect graph theorem characterizing all perfect graphs. The independence number and domination number of a rook's graph, or in other words the maximum number of rooks that can be placed so that they do not attack each other or so that they attack all remaining board squares, both equal the smaller of the chessboard's two dimensions, and these 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 rook's graph represents the moves of a rook on an chessboard. Its vertices represent the squares of the chessboard, and may be