Rook Graph


The m×n rook graph (confusingly called the m×n grid by Brouwer et al. 1989, p. 440) and also sometimes known as a lattice graph (e.g., Brouwer) is the graph Cartesian product K_m square K_n of complete graphs, which is equivalent to the line graph L(K_(m,n)) of the complete bipartite graph K_(m,n). This is the definition adopted for example by Brualdi and Ryser (1991, p. 153), although restricted to the case m=n. 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 m×n chessboard.

The graph K_m square K_n has mn vertices and mn(m+n)/2-mn edges. It is regular of degree m+n-2, has diameter 3, girth 3 (for max(m,n)>=3), and chromatic number max(m,n). It is also perfect (since it is the line graph of a bipartite graph) and vertex-transitive.

Define an n×n Latin square graph as a graph whose vertices are the n^2 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 n×n rook graph and the minimum vertex colorings of the n×n rook graph give the distinct n×n Latin squares.

n×n 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 K_m square K_n is a circulant graph iff (m,n)=1 (i.e., m is relatively prime to n). In that case, the rook graph is isomorphic to Ci_(mn)(m,2m,3m,...,mn/2,n,2n,3n,...,mn/2).

Special cases are summarized in the following table.

The following table summarized the bipartite double graphs of the rook graph K_2 square K_n for small n.

A closed formula for the number of 7-cycles of K_n square K_n is given by


(Perepechko and Voropaev).

The m×n rook graph has domination number gamma=min(m,n).

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

See also

Bishop Graph, Black Bishop Graph, Grid Graph, King Graph, Knight Graph, Rook Complement Graph, Square Graph, Triangular Graph, White Bishop Graph

Portions of this entry contributed by Stan Wagon

Explore with Wolfram|Alpha


Aubert, J. and Schneider, B. "Décomposition de la somme cartésienne d'un cycle et de l'union de deux cycles hamiltoniens en cycles hamiltoniens." Disc. Math. 38, 7-16, 1982.Brouwer, A. E. "Lattice Graphs.", A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.Brouwer, A. E. and van Lint, J. H. "Strongly Regular Graphs and Partial Geometries." In Enumeration and Design: Papers from the conference on combinatorics held at the University of Waterloo, Waterloo, Ont., June 14-July 2, 1982 (Ed. D. M. Jackson and S. A. Vanstone). Toronto, Canada: Academic Press, pp. 85-122, 1984.Brualdi, R. and Ryser, H. J. §6.2.4 in Combinatorial Matrix Theory. New York: Cambridge University Press, p. 152, 1991.Godsil, C. and Royle, G. "Latin Square Graphs." §10.4 Algebraic Graph Theory. New York: Springer-Verlag, pp. 226-230, 2001.Karavaev, A. M. "FlowProblem: Statistics of Simple Cycles.", S. N. and Voropaev, A. N. "The Number of Fixed Length Cycles in an Undirected Graph. Explicit Formulae in Case of Small Lengths."van Dam, E. R. and Haemers, W. H. "Which Graphs Are Determined by Their Spectrum?" Lin. Algebra Appl. 373, 139-162, 2003.

Cite this as:

Wagon, Stan and Weisstein, Eric W. "Rook Graph." From MathWorld--A Wolfram Web Resource.

Subject classifications