The 
rook graph (confusingly called
the 
grid by Brouwer et al. 1989,
p. 440) and also sometimes known as a lattice graph (e.g., Brouwer) is the graph Cartesian product 
of complete graphs,
which is equivalent to the line graph 
of the complete
bipartite graph 
.
This is the definition adopted for example by Brualdi and Ryser (1991, p. 153),
although restricted to the case 
. This definition corresponds to the connectivity graph of
a rook chess piece (which can move any number of spaces in a straight line-either
horizontally or vertically, but not diagonally) on an 
chessboard.
The graph 
has 
vertices and 
edges. It is regular of degree 
, has diameter 3, girth 3 (for 
), and chromatic
number 
.
It is also perfect (since it is the line
graph of a bipartite graph) and vertex-transitive.
Define an 
Latin square graph as a graph whose vertices are the 
elements of the Latin square
and such that two vertices being are if they lie in the same row or column or contain
the same symbol. These graphs correspond to the 
rook graph and the minimum
vertex colorings of the 
rook graph give the distinct 
Latin squares.
rook graphs are distance-regular
and geometric.
Precomputed properties of rook graphs are implemented in the Wolfram Language as GraphData[
"Rook", 
m, n
].
A rook graph 
is a circulant graph iff 
(i.e., 
is relatively prime to
). In that case, the rook graph is isomorphic
to 
.
Special cases are summarized in the following table.
 | isomorphic to |
 | square graph  |
 | prism
graph  |
 | circulant graph  |
 | graph
complement of the  -crown graph |
 | generalized quadrangle  |
 | circulant
graph  |
 | 25-cyclotomic graph |
The following table summarized the bipartite double graphs of the rook graph 
for small 
.
A closed formula for the number of 7-cycles of 
is given by
 |
(Perepechko and Voropaev).
The 
rook graph has domination
number 
.
Aubert and Schneider (1982) showed that rook graphs admit Hamiltonian decomposition, meaning they are class 1 when they have even vertex count and class 2 when they have odd vertex count (because they are odd regular).
