Rook's graph

Rook's graph
8x8 Rook's graph
Vertices	$nm$
Edges	$nm (n + m)/2 - nm$
Diameter	$2$
Girth	$3$ (if $max(n, m) \geq 3$ )
Chromatic number	$max(n, m)$
Properties	regular, vertex-transitive, perfect well-covered

In graph theory, a rook's graph is a graph that represents all legal moves of the rook chess piece on a chessboard: each vertex represents a square on a chessboard and each edge represents a legal move. Rook's graphs are highly symmetric perfect graphs; they may be characterized in terms of the number of triangles each edge belongs to and by the existence of a $4$ -cycle connecting each nonadjacent pair of vertices.

An $n \times m$ rook's graph represents the moves of a rook on an $n \times m$ chessboard. Its vertices may be given coordinates $(x, y)$ , where $1 \leq x \leq n$ and $1 \leq y \leq m$ . Two vertices $(x 1, y 1)$ and $(x 2, y 2)$ are adjacent if and only if either $x 1 = x 2$ or $y 1 = y 2$ ; that is, if they belong to the same rank or the same file of the chessboard.

For an $n \times m$ rook's graph the total number of vertices is simply $nm$ . For an $n \times n$ rook's graph the total number of vertices is simply $n 2$ and the total number of edges is $n 3 - n 2$ ; in this case the graph is also known as a two-dimensional Hamming graph or a Latin square graph.

The rook's graph for an $n \times m$ chessboard may also be defined as the Cartesian product of two complete graphs $K n$ and $K m$ , expressed in a single formula as $K n ◻ K m$ . The complement graph of a $2 \times n$ rook's graph is a crown graph.

...
Wikipedia