Rook's Graph

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 of a rook's graph represents a square on a chessboard, and each edge connects two squares on the same row (rank) or on the same column (file) as each other, the squares that a rook can move between. These graphs can be constructed for chessboards of any rectangular shape, and can be defined mathematically as the Cartesian product of two complete graphs, as the two-dimensional Hamming graphs, or as the line graphs of complete bipartite 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 (they are distance-transitive). For chessboards with relatively prime dimensions, they are circulant graphs. With one exception, they can be distinguished from all other graphs by the numbers of triangles each edge belongs to and by the existence of a -cycle connecting each nonadjacent pair of vertices.

Rook's graphs are perfect graphs, meaning that every subset of chessboard squares can be colored so that no two squares in a row or column have the same color, and so that the number of colors equals the maximum number of squares from the subset in any single row or column (the clique number of an induced subgraph). The graphs formed in this way from subsets of squares in a rook's graph form one of the key components of a decomposition of perfect graphs used to prove the strong perfect graph theorem characterizing all perfect graphs. The independence number and domination number of a rook's graph, or in other words the maximum number of rooks that can be placed so that they do not attack each other or so that they attack all remaining board squares, both equal the smaller of the chessboard's two dimensions, and these 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.

Definition and mathematical constructions

An rook's graph represents the moves of a rook on an chessboard.
Its vertices represent the squares of the chessboard, and may be given coordinates , where and . Two vertices with coordinates and are adjacent if and only if either (the two squares belong to the same file of the chessboard, and are connected by a vertical rook move) or (the two squares belong to the same rank and are connected by a horizontal move).

Within a single rank or a single file of the chessboard, all squares are reachable from each other, so these squares form a clique, a subset of vertices forming a complete graph. The whole rook's graph for an chessboard can be formed from these two kinds of cliques as the Cartesian product of graphs . Because the rook's graph for a square chessboard is the Cartesian product of equal-size cliques, it is an example of a Hamming graph. Its dimension as a Hamming graph is two, and every two-dimensional Hamming graph is a rook's graph for a square chessboard. Square chessboard graphs are also called Latin square graphs, because the vertices of such a graph describe the squares of a Latin square and its edges describe pairs of squares that cannot contain the same value. The Sudoku graphs are supergraphs of Rook's graphs with some additional edges, connecting squares of a Sudoku puzzle that should have unequal values.

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. For instance, the 3-3 duoprism is a four-dimensional shape formed as the Cartesian product of two triangles, and has a rook's graph as its skeleton.

Regularity and symmetry

Strong regularity

and observe that the $m\times n$ rook's graph has all of the following properties:
*It has $mn$ vertices, one for each square of the $m\times n$ chessboard. Each vertex is adjacent to $m+n-2$ edges, connecting it to the $m-1$ squares on the same rank and the $n-1$ squares on the same file.
*The triangles within the rook's graph are formed by triples of squares within a single rank or file. When $m\ne n$, exactly $n\tbinom$ edges (the ones connecting squares on the same rank) belong to $m-2$ triangles; the remaining $m\tbinom$ edges (the ones connecting squares on the same file) belong to $n-2$ triangles. When $m=n$, each edge belongs to $m-2=n-2$ triangles.
*Every two vertices that are not adjacent to each other belong to a unique $4$-vertex cycle, connected to each other through the other two vertices that use a combination of the same two ranks and files.
As they show, except in the case $m=n=4$, these properties uniquely characterize the rook's graph. That is, the rook's graphs are the only graphs with these numbers of vertices, edges, triangles per edge, and with a unique 4-cycle through each two non-adjacent vertices.

When $m=n$, these conditions may be abbreviated by stating that an $n\times n$ rook's graph is a strongly regular graph with parameters
$\operatorname(n^2,2n-2,n-2,2)$. These parameters describe the number of vertices, the number of edges per vertex, the number of triangles per edge, and the number of shared neighbors for two non-adjacent vertices, respectively. Conversely, every strongly regular graph with these parameters must be an $n\times n$ rook's graph, unless $n=4$.

When $n=4$, there is another strongly regular graph, the Shrikhande graph, with the same parameters as the $4\times 4$ rook's graph.
The Shrikhande graph obeys the same properties listed by Moon and Moser. It can be distinguished from the $4\times 4$ rook's graph in that the neighborhood of each vertex in the Shrikhande graph is connected to form a . In contrast, in the $4\times 4$ rook's graph, the neighborhood of each vertex forms two triangles, one for its rank and another for its file, without any edges from one part of the neighborhood to the other. Another way of distinguishing the $4\times 4$ rook's graph from the Shrikhande graph uses clique cover numbers: the $n=4$ 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.

Symmetry

Rook's graphs are vertex-transitive and $(m+n-2)$- regular; they are the only regular graphs formed from the moves of standard chess pieces in this way. When $m\ne n$, the symmetries of the rook's graph are formed by independently permuting the rows and columns of the graph, so the automorphism group of the graph has $m!n!$ elements. When $m=n$, the graph has additional symmetries that swap the rows and columns, so the number of automorphisms is $2n!^2$.

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. Any two nonadjacent vertices may be transformed into any other two nonadjacent vertices by a symmetry of the graph. 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.

When $m$ and $n$ are relatively prime, the symmetry group $S_m\times S_n$ of the rook's graph contains as a subgroup the cyclic group $C_=C_m\times C_n$ that acts by cyclically permuting the $mn$ vertices; therefore, in this case, the rook's graph is a circulant graph.

Square rook's graphs are connected-homogeneous, meaning that every isomorphism between two connected induced subgraphs can be extended to an automorphism of the whole graph.

Other properties

Perfection

A rook's graph can also be viewed as the line graph of a complete bipartite graph — that is, it has one vertex for each edge of , and two vertices of the rook's graph are adjacent if and only if the corresponding edges of the complete bipartite graph share a common endpoint. In this view, an edge in the complete bipartite graph from the th vertex on one side of the bipartition to the th vertex on the other side corresponds to a chessboard square with coordinates .

Any bipartite graph is a subgraph of a complete bipartite graph, and correspondingly any line graph of a bipartite graph is an induced subgraph of a rook's graph. 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. Line graphs of bipartite graphs form an important family of perfect graphs: they are one of a small number of families used by to characterize the perfect graphs and to show that every graph with no odd hole and no odd antihole is perfect. In particular, rook's graphs are themselves perfect.

Because a rook's graph is perfect, the number of colors needed in any coloring of the graph is just the size of its largest clique. 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 , so this is also the chromatic number of the graph. An -coloring of an rook's graph may be interpreted as a Latin square: it describes a way of filling the rows and columns of an grid with different values in such a way that the same value does not appear twice in any row or column. Although finding an optimal coloring of a rook's graph is straightforward, it is NP-complete to determine whether a partial coloring can be extended to a coloring of the whole graph (this problem is called precoloring extension). Equivalently, it is NP-complete to determine whether a partial Latin square can be completed to a full Latin square.

Independence

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. Perfect graphs may also be described as the graphs in which, in every induced subgraph, the size of the largest independent set is equal to the number of cliques in a partition of the graph's vertices into a minimum number of cliques. In a rook's graph, the sets of rows or the sets of columns (whichever has fewer sets) form such an optimal partition. The size of the largest independent set in the graph is therefore . Every color class in every optimal coloring of a rook's graph is a maximum independent set.

Rook's graphs are well-covered graphs: every independent set in a rook's graph can be extended to a maximum independent set, and every maximal independent set in a rook's graph has the same size, .

Domination

The domination number of a graph is the minimum cardinality among all dominating sets. 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 board. For the board the domination number is .

On the rook's graph a -dominating set is a set of vertices whose corresponding squares attack all other squares (via a rook's move) at least times. A -tuple dominating set on the rook's graph is a set of vertices whose corresponding squares attack all other squares at least times and are themselves attacked at least times. The minimum cardinality among all -dominating and -tuple dominating sets are the -domination number and the -tuple domination number, respectively. On the square board, and for even , the -domination number is when and . In a similar fashion, the -tuple domination number is when is odd and less than .

Spectrum

The spectrum of a rook's graph (the eigenvalues of its adjacency matrix) consists of the four eigenvalues $m+n-2$, $m-2$, $n-2$, and $-2$. Because these are all integers, rook's graphs are integral graphs. There are only three classes of graphs (and finitely many exceptional graphs) that can have four eigenvalues with one of the four being $-2$; one of the three classes is the class of rook's graphs. For most combinations of $m$ and $n$, the $m\times n$ rook's graph is spectrally unique: no other graph has the same spectrum. In particular this is true when $n=2$ or $n=m-1$, or when the two numbers $m$ and $n$ sum to at least 18 and do not have the form $2t^2\pm t$.

See also

* King's graph, knight's graph, queen's graph, and bishop's graph, four other graphs defined from the moves of chess pieces
* Lattice graph, the graph of horizontal and vertical adjacencies of squares on a chessboard

References

External links

*{{mathworld, title=Lattice Graph, urlname=LatticeGraph, mode=cs2

Mathematical chess problems
Perfect graphs
Parametric families of graphs
Regular graphs
Strongly regular graphs