The 
rook graph is the graph
Cartesian product 
of complete graphs, where 
and 
are positive integers. It is also called the
grid (Brouwer et al. 1989,
p. 440) or a lattice graph (e.g., Brouwer). By analogy with the KC
graph and KP graph, the 
rook graph could also be called a "KK graph."
It is equivalent to the line graph 
of the complete
bipartite graph 
,
which is the definition adopted for example by Brualdi and Ryser (1991, p. 153)
(although restricted to the case 
).
The name of the graph derives from the fact that it 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.
Attractive embeddings of small 
rook graphs are illustrated above.
The graph 
has 
vertices and 
edges. It is regular
of vertex degree 
and has chromatic number 
. Its diameter
is 2 when both 
,
1 when exactly one dimension is 1 and the other exceeds 1, and 0 when 
. Its girth is 3 for 
. It is also perfect
(since it is the line graph of a bipartite
graph) and vertex-transitive.
The Latin square graph associated with a Latin square of order 
has its 
cells as vertices. Distinct
vertices are adjacent
if they share a row or column or contain the same symbol. For 
, this graph strictly contains
the 
rook graph as a spanning
subgraph. Minimum vertex colorings
of the rook graph using a fixed set of 
colors correspond to Latin squares
of order 
.
rook graphs are distance-regular
and geometric.
Precomputed properties of rook graphs are implemented in the Wolfram Language as GraphData[
"Rook", 
m, n
].
If 
and 
are relatively prime,
the rook graph 
is isomorphic to a circulant
graph on 
vertices, with offsets given by all positive multiples
of 
or 
not exceeding 
. The square graph 
is also a circulant
graph, although its dimensions are not relatively
prime.
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 summarizes the bipartite double graphs of the rook graph 
for small 
. Each bipartite double
graph has 
vertices, twice the vertex
count of the original rook graph.
 | bipartite double graph of  |
| 2 |  |
| 3 | prism
graph  |
| 4 | tesseract
graph  |
| 5 | Haar
graph  |
A closed formula for the number of 7-cycles of 
is given by
 |
(Voropaev and Perepechko).
The 
rook graph has domination
number 
.
Furthermore, its domination polynomial is
given in closed form by
![D_(K_m square K_n)(x)=[(1+x)^n-1]^m-(-1)^msum_(k=0)^(m-1)(-1)^k(m; k)[(1+x)^k-1]^n](/images/equations/RookGraph/NumberedEquation2.svg) |
(Mertens 2024, p. 5).
Aubert and Schneider (1981) showed that rook graphs with 
admit Hamilton
decompositions, using the extended convention that permits a single perfect
matching for odd vertex degree. For positive
integers 
and 
, a rook graph is class
1 when 
is even, and class 2 when 
is odd and greater than 1. The singleton
graph 
is class 1.
en cycles hamiltoniens."
Disc. Math. 37, 19-27, 1981.