Rook's graph

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.