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

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.

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

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.

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

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

[4] The Sudoku graphs are rook's graphs with some additional edges, connecting squares of a Sudoku puzzle that should have unequal values.

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

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

[10] The Shrikhande graph obeys the same properties listed by Moon and Moser.

rook's graph can be covered by four cliques (the four ranks or the four files of the chessboard) whereas six cliques are needed to cover the Shrikhande graph.

, the graph has additional symmetries that swap the rows and columns, so the number of automorphisms is

[13] Any two vertices in a rook's graph are either at distance one or two from each other, according to whether they are adjacent or nonadjacent respectively.

When the rook's graph is not square, the pairs of adjacent vertices fall into two orbits of the symmetry group according to whether they are adjacent horizontally or vertically, but when the graph is square any two adjacent vertices may also be mapped into each other by a symmetry and the graph is therefore distance-transitive.

[2][17] In this view, an edge in the complete bipartite graph from the ith vertex on one side of the bipartition to the jth vertex on the other side corresponds to a chessboard square with coordinates (i, j).

[18] The line graphs of bipartite graphs are perfect: in them, and in any of their induced subgraphs, the number of colors needed in any vertex coloring is the same as the number of vertices in the largest complete subgraph.

The cliques of a rook's graph are the subsets of a single row or a single column, and the largest of these have size max(m, n), so this is also the chromatic number of the graph.

An n-coloring of an n × n rook's graph may be interpreted as a Latin square: it describes a way of filling the rows and columns of an n × n grid with n different values in such a way that the same value does not appear twice in any row or column.

[20] In the same way, a coloring of a rectangular rook's graph corresponds to a Latin rectangle.

[22] An independent set in a rook's graph is a set of vertices, no two of which belong to the same row or column of the graph; in chess terms, it corresponds to a placement of rooks no two of which attack each other.

The size of the largest independent set in the graph is therefore min(m, n).

On the rook's graph a set of vertices is a dominating set if and only if their corresponding squares either occupy, or are a rook's move away from, all squares on the m × n board.

[24] On the rook's graph a k-dominating set is a set of vertices whose corresponding squares attack all other squares (via a rook's move) at least k times.

A k-tuple dominating set on the rook's graph is a set of vertices whose corresponding squares attack all other squares at least k times and are themselves attacked at least k − 1 times.

The minimum cardinality among all k-dominating and k-tuple dominating sets are the k-domination number and the k-tuple domination number, respectively.

In a similar fashion, the k-tuple domination number is n(k + 1)/2 when k is odd and less than 2n.

[26] However, these cycles may involve moves between squares that are far apart within a single row or column of the chessboard.

Instead, the study of "rook's tours", in the mathematics of chess, has generally concentrated on a special case of these Hamiltonian cycles where the rook is restricted to move only to adjacent squares.

These single-step rook's tours only exist on boards with an even number of squares.

They play a central role in the proof of Gomory's theorem that, if two squares of opposite colors are removed from a standard chessboard, the remaining squares can always be covered by dominoes.