View source for Rook's graph

{{good article}}
{{Short description|Graph of chess rook moves}}
{{Use mdy dates|cs1-dates=ly|date=May 2023}}
{{Use list-defined references|date=May 2023}}
{{infobox graph
 | name = Rook's graph
 | image = Rook's graph.svg
 | image_caption = 8x8 Rook's graph
 | vertices = {{math|''nm''}}
 | edges = {{math|''nm''(''n'' + ''m'')/2 &minus; ''nm''}}
 | diameter = {{math|2}}
 | chromatic_number = {{math|max(''n'', ''m'')}}
 | chromatic_index = 
 | girth = {{math|3}} (if {{math|max(''n'', ''m'') ≥ 3}})
 | spectrum = {{math|{''m'' + ''n'' &minus; 2, ''m'' &minus; 2, ''n'' &minus; 2, &minus;2}{{void}}}}
 | properties = {{plainlist|1=
*[[integral graph|integral]]
*[[perfect graph|perfect]]
*[[regular graph|regular]]
*[[vertex-transitive graph|vertex-transitive]]
*[[well-covered graph|well-covered]]
}}
}}
In [[graph theory]], a '''rook's graph''' is an [[undirected graph]] that represents all legal moves of the [[Rook (chess)|rook]] [[chess piece]] on a [[chessboard]]. Each [[vertex (graph theory)|vertex]] of a rook's graph represents a square on a chessboard, and there is an [[edge (graph theory)|edge]] between any two squares sharing a row (rank) or column (file), the squares that a rook can move between. These graphs can be constructed for chessboards of any rectangular shape. Although rook's graphs have only minor significance in chess lore, they are more important in the abstract mathematics of graphs through their alternative constructions: rook's graphs are the [[Cartesian product of graphs|Cartesian product]] of two [[complete graph]]s, and are the [[line graph]]s of [[complete bipartite graph]]s. The square rook's graphs constitute the two-dimensional [[Hamming graph]]s.

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 in moves (making the graph [[distance-transitive graph|distance-transitive]]). For rectangular chessboards whose width and height are [[relatively prime numbers|relatively prime]], the rook's graphs are [[circulant graph]]s. With one exception, the rook's graphs can be distinguished from all other graphs using only two properties: the numbers of triangles each edge belongs to, and the existence of a unique {{math|4}}-[[Cycle (graph theory)|cycle]] connecting each nonadjacent pair of vertices.

Rook's graphs are [[perfect graph]]s. In other words, every subset of chessboard squares can be [[graph coloring|colored]] so that no two squares in a row or column have the same color, using a number of colors equal to the maximum number of squares from the subset in any single row or column (the [[clique number]] of the [[induced subgraph]]). This class of induced subgraphs are a key component of a decomposition of perfect graphs used to prove the [[strong perfect graph theorem]], which characterizes all perfect graphs. The [[independence number]] and [[domination number]] of a rook's graph both equal the smaller of the chessboard's width and height. In terms of chess, the independence number is the maximum number of rooks that can be placed without attacking each other; the domination number is the minimum number needed to attack all unoccupied board squares. Rook's graphs are [[well-covered graph]]s, 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 {{math|''n'' × ''m''}} rook's graph represents the moves of a rook on an {{math|''n'' × ''m''}} chessboard.{{r|lw}}
Its vertices represent the squares of the chessboard, and may be given coordinates {{math|(''x'', ''y'')}}, where {{math|1 ≤ ''x'' ≤ ''n''}} and {{math|1 ≤ ''y'' ≤ ''m''}}. Two vertices with coordinates {{math|(''x''<sub>1</sub>, ''y''<sub>1</sub>)}} and {{math|(''x''<sub>2</sub>, ''y''<sub>2</sub>)}} are adjacent if and only if either {{math|1=''x''<sub>1</sub> = ''x''<sub>2</sub>}} or {{math|1=''y''<sub>1</sub> = ''y''<sub>2</sub>}}. (If {{math|1=''x''<sub>1</sub> = ''x''<sub>2</sub>}}, the vertices share a file and are connected by a vertical rook move; if {{math|1=''y''<sub>1</sub> = ''y''<sub>2</sub>}}, they share a rank and are connected by a horizontal rook move.){{r|lw}}

The squares of a single rank or file are all directly connected to each other, so each rank and file forms a [[clique (graph theory)|clique]]—a subset of vertices forming a [[complete graph]]. The whole rook's graph for an {{math|''n'' × ''m''}} chessboard can be formed from these two kinds of cliques, as the [[Cartesian product of graphs]] {{math|''K''<sub>''n''</sub> ◻ ''K''<sub>''m''</sub>}}.{{r|stones}} 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.{{r|ae}} Square rook's graphs are also called "[[Latin square]] graphs"; applied to a Latin square, its edges describe pairs of squares that cannot contain the same value.{{r|gs}} The [[Sudoku graph]]s are rook's graphs with some additional edges, connecting squares of a Sudoku puzzle that should have unequal values.{{r|hm}}

[[File:Triangular Duoprism YW and ZW Rotations.gif|thumb|The [[3-3 duoprism]], a four-dimensional [[convex polytope]] having a {{math|3 × 3}} rook's graph as its skeleton]]
Geometrically, the rook's graphs can be formed by sets of the vertices and edges (the [[n-skeleton|skeletons]]) of a family of [[convex polytope]]s, the Cartesian products of pairs of [[neighborly polytope]]s.{{r|mpp}} For instance, the [[3-3 duoprism]] is a four-dimensional shape formed as the Cartesian product of two [[triangle]]s, and has a {{math|3 × 3}} rook's graph as its skeleton.{{r|simploid}}

==Regularity and symmetry==
===Strong regularity===
{{harvtxt|Moon|1963}} and {{harvtxt|Hoffman|1964}} observe that the <math>m\times n</math> rook's graph (or equivalently, as they describe it, the line graph of the complete bipartite graph <math>K_{m,n}</math>) has all of the following properties:
*It has <math>mn</math> vertices, one for each square of the <math>m\times n</math> chessboard. Each vertex is adjacent to <math>m+n-2</math> edges, connecting it to the <math>m-1</math> squares on the same rank and the <math>n-1</math> 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 <math>m\ne n</math>, exactly <math>n\tbinom{m}{2}</math> edges (the ones connecting squares on the same rank) belong to <math>m-2</math> triangles; the remaining <math>m\tbinom{n}{2}</math> edges (the ones connecting squares on the same file) belong to <math>n-2</math> triangles. When <math>m=n</math>, each edge belongs to <math>m-2=n-2</math> triangles.
*Every two nonadjacent vertices belong to a unique <math>4</math>-vertex [[cycle (graph theory)|cycle]], namely the only rectangle using the two vertices as corners.
They show that except in the case <math>m=n=4</math>, 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.{{r|moon|hoffman}}

When <math>m=n</math>, these conditions may be abbreviated by stating that an <math>n\times n</math> rook's graph is a [[strongly regular graph]] with parameters
<math>\operatorname{srg}(n^2,2n-2,n-2,2)</math>. 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.{{r|lw}} Conversely, every strongly regular graph with these parameters must be an <math>n\times n</math> rook's graph, unless <math>n=4</math>.{{r|moon|hoffman}}

[[File:Shrikhande torus.svg|thumb|upright=1.35|The [[Shrikhande graph]] embedded on a torus. This is not a rook's graph, but is strongly regular with the same parameters as the <math>4\times 4</math> rook's graph.]]
When <math>n=4</math>, there is another strongly regular graph, the [[Shrikhande graph]], with the same parameters as the <math>4\times 4</math> rook's graph.{{r|fw}}
The Shrikhande graph obeys the same properties listed by Moon and Moser. It can be distinguished from the <math>4\times 4</math> rook's graph in that the [[neighborhood (graph theory)|neighborhood]] of each vertex in the Shrikhande graph is connected to form a {{nowrap|<math>6</math>-cycle}}. In contrast, in the <math>4\times 4</math> 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.{{r|bm}} Another way of distinguishing the <math>4\times 4</math> rook's graph from the Shrikhande graph uses [[clique cover]] numbers: the <math>n=4</math> 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.{{r|fw}}

===Symmetry===
Rook's graphs are [[Vertex-transitive graph|vertex-transitive]], meaning that they have symmetries taking every vertex to every other vertex. This implies that every vertex has an equal number of edges: they are <math>(m+n-2)</math>-[[Regular graph|regular]]. The rook's graphs are the only regular graphs formed from the moves of standard chess pieces in this way.{{r|elkies}} When <math>m\ne n</math>, the symmetries of the rook's graph are formed by independently permuting the rows and columns of the graph, so the [[graph automorphism|automorphism group]] of the graph has <math>m!n!</math> elements. When <math>m=n</math>, the graph has additional symmetries that swap the rows and columns, so the number of automorphisms is <math>2n!^2</math>.{{r|harary}}

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 [[orbit (group theory)|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 graph|distance-transitive]].{{r|biggs}}

When <math>m</math> and <math>n</math> are [[relatively prime]], the symmetry group <math>S_m\times S_n</math> of the rook's graph contains as a subgroup the [[cyclic group]] <math>C_{mn}=C_m\times C_n</math> that [[Group action (mathematics)|acts]] by cyclically permuting the <math>mn</math> vertices. Therefore, in this case, the rook's graph is a [[circulant graph]].{{r|bh}}

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

==Other properties==
===Perfection===
[[File:Paley9-perfect.svg|thumb|left|The 3&times;3 rook's graph (the graph of the [[3-3 duoprism]]), colored with three colors and showing a clique of three vertices. In this graph and each of its induced subgraphs the chromatic number equals the clique number, so it is a perfect graph.]]
A rook's graph can also be viewed as the [[line graph]] of a [[complete bipartite graph]] {{math|''K''<sub>''n'',''m''</sub>}} — that is, it has one vertex for each edge of {{math|''K''<sub>''n'',''m''</sub>}}, 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.{{r|stones|dewerra}} In this view, an edge in the complete bipartite graph from the {{mvar|i}}th vertex on one side of the bipartition to the {{mvar|j}}th vertex on the other side corresponds to a chessboard square with coordinates {{math|(''i'', ''j'')}}.{{r|lw}}

Any [[bipartite graph]] is a [[Glossary of graph theory#Subgraphs|subgraph]] of a complete bipartite graph, and correspondingly any line graph of a bipartite graph is an [[induced subgraph]] of a rook's graph.{{sfnp|de Werra|Hertz|1999}} The line graphs of bipartite graphs are [[perfect graph|perfect]]: in them, and in any of their induced subgraphs, the number of colors needed in any [[graph coloring|vertex coloring]] is the same as the number of vertices in the largest [[clique (graph theory)|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 {{harvtxt|Chudnovsky|Robertson|Seymour|Thomas|2006}} to characterize the perfect graphs and to show that every graph with no odd hole and no odd antihole is perfect.{{r|crst}} In particular, rook's graphs are themselves perfect.

[[File:Z2^3; Cayley table; colors.svg|thumb|upright|8-coloring of a chessboard graph obtained from a [[Cayley table]] of a [[finite group]]]]
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 {{math|max(''m'', ''n'')}}, so this is also the chromatic number of the graph. An {{mvar|n}}-coloring of an {{math|''n'' &times; ''n''}} rook's graph may be interpreted as a [[Latin square]]: it describes a way of filling the rows and columns of an {{math|''n'' &times; ''n''}} grid with {{mvar|n}} different values in such a way that the same value does not appear twice in any row or column.{{r|lsww}} In the same way, a coloring of a rectangular rook's graph corresponds to a [[Latin rectangle]].{{r|stone}} 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.{{r|colbourn}}

===Independence===
{{Chess diagram
| tright
|
|__|__|__|rl|__|__|__|__
|__|__|__|__|__|__|rl|__
|__|__|rl|__|__|__|__|__
|rl|__|__|__|__|__|__|__
|__|rl|__|__|__|__|__|__
|__|__|__|__|__|__|__|rl
|__|__|__|__|rl|__|__|__
|__|__|__|__|__|rl|__|__
|A non-attacking placement of eight rooks on a chessboard, forming a maximum independent set in the corresponding rook's graph
}}
An [[Independent set (graph theory)|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 {{math|min(''m'', ''n'')}}.{{r|lw}} 

Rook's graphs are [[well-covered graph]]s: every [[independent set (graph theory)|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, {{math|min(''m'', ''n'')}}.{{r|lpp}}

===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 {{math|''m'' &times; ''n''}} board. For the {{math|''m'' &times; ''n''}} board the domination number is {{math|min(''m'', ''n'')}}.{{r|yy}}

On the rook's graph a {{mvar|k}}-dominating set is a set of vertices whose corresponding squares attack all other squares (via a rook's move) at least {{mvar|k}} times. A {{mvar|k}}-tuple dominating set on the rook's graph is a set of vertices whose corresponding squares attack all other squares at least {{mvar|k}} times and are themselves attacked at least {{math|''k'' &minus; 1}} times. The minimum cardinality among all {{mvar|k}}-dominating and {{mvar|k}}-tuple dominating sets are the {{mvar|k}}-domination number and the {{mvar|k}}-tuple domination number, respectively. On the square board, and for even {{mvar|k}}, the {{mvar|k}}-domination number is {{math|''nk''/2}} when {{math|''n'' ≥ (''k''<sup>2</sup> &minus; 2''k'')/4}} and {{math|''k'' < 2''n''}}. In a similar fashion, the {{mvar|k}}-tuple domination number is {{math|''n''(''k'' + 1)/2}} when {{mvar|k}} is odd and less than {{math|2''n''}}.{{r|bll}}

===Hamiltonicity===
Every rook's graph contains a [[Hamiltonian cycle]].{{r|ho}} However, these cycles may involve moves between squares that are far apart within a single row or column of the chessboard. Instead, the study of "rook's tours", in the mathematics of chess, has generally concentrated on a special case of these Hamiltonian cycles where the rook is restricted to move only to adjacent squares. These single-step rook's tours only exist on boards with an even number of squares. They play a central role in the proof of [[Gomory's theorem]] that, if two squares of opposite colors are removed from a standard chessboard, the remaining squares can always be covered by dominoes.{{r|w}} They are featured alongside [[knight's tour]]s in the first work to discuss chess-piece tours, the 9th century Sanskrit ''Kavyalankara'' of [[Rudrata]].{{r|bcm}}

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

==In other graphs==
The graphs for which the [[Neighbourhood (graph theory)|neighbors]] of each vertex [[induced subgraph|induce]] a rook's graph have been called ''locally grid''. Examples include the [[Johnson graph]]s <math>J(n,k)</math>, for which the neighbors of each vertex form a <math>k\times(n-k)</math> rook's graph. Other examples are known, and for some rook's graphs, a complete classification is known. For instance, there are two graphs whose neighborhoods are all <math>3\times 3</math> rook's graphs: they are the Johnson graph <math>J(6,3)</math>, and the [[complement graph]] of a <math>4\times 4</math> rook's graph.{{r|cohen}}

== See also ==
* [[Bishop's graph]]
* [[Chessboard complex]], the [[independence complex]] of the rook's graph
* [[King's graph]]
* [[Knight's graph]]
* [[Lattice graph]], the graph of horizontal and vertical adjacencies of squares on a chessboard
* [[Queen's graph]]

== References ==
{{reflist|refs=

<ref name=ae>{{citation
 | last1 = Azizoğlu | first1 = M. Cemil
 | last2 = Eğecioğlu | first2 = Ömer
 | doi = 10.1137/S0895480100375053
 | issue = 2
 | journal = [[SIAM Journal on Discrete Mathematics]]
 | mr = 2032290
 | pages = 219–236
 | title = Extremal sets minimizing dimension-normalized boundary in Hamming graphs
 | volume = 17
 | year = 2003}}.</ref>

<ref name=bcm>{{citation|magazine=The British Chess Magazine|volume=22|issue=1|date=January 1902|url=https://books.google.com/books?id=wolJAAAAYAAJ&pg=PA1|title=The knight's tour: ancient and oriental|pages=1–7|first=H. J. R.|last=Murray}}</ref>

<ref name=bh>This follows from the definition of the rook's graph as a Cartesian product graph, together with Proposition 4 of {{citation
 | last1 = Broere | first1 = Izak
 | last2 = Hattingh | first2 = Johannes H.
 | doi = 10.1080/16073606.1990.9631612
 | issue = 2
 | journal = Quaestiones Mathematicae
 | mr = 1068710
 | pages = 191–216
 | title = Products of circulant graphs
 | volume = 13
 | year = 1990}}.</ref>

<ref name=biggs>{{citation
 | last = Biggs | first = Norman | author-link = Norman L. Biggs
 | journal = Utilitas Mathematica
 | mr = 0347684
 | pages = 113–121
 | title = The symmetry of line graphs
 | volume = 5
 | year = 1974}}.</ref>

<ref name=bll>{{citation
 | last1 = Burchett | first1 = Paul
 | last2 = Lane | first2 = David
 | last3 = Lachniet | first3 = Jason
 | title = {{mvar|K}}-domination and {{mvar|k}}-tuple domination on the rook's graph and other results
 | year = 2009
 | journal = Congressus Numerantium
 | volume = 199
 | pages = 187–204}}.</ref>

<ref name=bm>{{citation
 | last1 = Burichenko | first1 = V. P.
 | last2 = Makhnev | first2 = A. A.
 | issue = 2
 | journal = [[Doklady Akademii Nauk]]
 | language = Russian
 | mr = 2953786
 | pages = 151–155
 | title = Об автоморфизмах сильно регулярных локально циклических графов
 | trans-title = On automorphisms of strongly regular locally cyclic graphs
 | volume = 441
 | year = 2011}}. Translated in ''Doklady Mathematics'' 84 (3): 778–782, 2011, {{doi|10.1134/S1064562411070076}}. From the first page of the translation: "The Shrikhande
graph is the only strongly regular locally hexagonal graph with parameters (16, 6, 2, 2)."</ref>

<ref name=cohen>{{citation
 | last = Cohen | first = Arjeh M.
 | editor1-last = Kantor | editor1-first = William M.
 | editor2-last = Liebler | editor2-first = Robert A.
 | editor3-last = Payne | editor3-first = Stanley E.
 | editor4-last = Shult | editor4-first = Ernest E.
 | contribution = Local recognition of graphs, buildings, and related geometries
 | contribution-url = https://pure.tue.nl/ws/files/1882013/588207.pdf
 | mr = 1072157
 | pages = 85–94
 | publisher = Oxford University Press
 | series = Oxford Science Publications
 | title = Finite Geometries, Buildings, and Related Topics: Papers from the Conference on Buildings and Related Geometries held in Pingree Park, Colorado, July 17–23, 1988
 | year = 1990}}; see in particular pp. 89–90</ref>

<ref name=colbourn>{{citation
 | last = Colbourn | first = Charles J. | author-link = Charles Colbourn
 | doi = 10.1016/0166-218X(84)90075-1
 | issue = 1
 | journal = [[Discrete Applied Mathematics]]
 | mr = 739595
 | pages = 25–30
 | title = The complexity of completing partial Latin squares
 | volume = 8
 | year = 1984| doi-access = free
 }}.</ref>

<ref name=crst>{{citation
 | last1 = Chudnovsky | first1 = Maria | author1-link = Maria Chudnovsky
 | authorlink2 = Neil Robertson (mathematician)| last2 = Robertson | first2 = Neil
 | authorlink3 = Paul Seymour (mathematician) | last3 = Seymour | first3 = Paul
 | last4 = Thomas | first4 = Robin | author4-link=Robin Thomas (mathematician)
 | doi = 10.4007/annals.2006.164.51
 | year = 2006
 | url = https://web.math.princeton.edu/~pds/papers/perfect/perfect.pdf
 | title = The strong perfect graph theorem
 | journal = [[Annals of Mathematics]]
 | jstor = 20159988
 | volume = 164
 | issue = 1
 | pages = 51–229| arxiv = math/0212070| s2cid = 119151552 }}.</ref>

<ref name=dewerra>For the equivalence between Cartesian products of complete graphs and line graphs of complete bipartite graphs, see {{citation
 | last1 = de Werra | first1 = D.
 | last2 = Hertz | first2 = A.
 | title = On perfectness of sums of graphs
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | volume = 195
 | year = 1999
 | issue = 1–3
 | pages = 93–101
 | url = http://www.gerad.ca/~alainh/Sum.pdf
 | doi = 10.1016/S0012-365X(98)00168-X | doi-access = free
 | mr = 1663807}}.</ref>

<ref name=doob>{{citation
 | last = Doob | first = Michael
 | doi = 10.1016/0024-3795(70)90037-6
 | journal = [[Linear Algebra and Its Applications]]
 | mr = 285432
 | pages = 461–482
 | title = On characterizing certain graphs with four eigenvalues by their spectra
 | volume = 3
 | year = 1970| issue = 4
 | doi-access = free
 }}</ref>

<ref name=fw>{{citation
 | last1 = Fiala | first1 = Nick C.
 | last2 = Haemers | first2 = Willem H.
 | doi = 10.1016/j.disc.2004.03.023
 | issue = 23
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 2273138
 | pages = 3083–3096
 | title = 5-chromatic strongly regular graphs
 | volume = 306
 | year = 2006| doi-access = free
 }}.</ref>

<ref name=elkies>{{citation
  | title = Graph theory glossary
  | url = http://www.math.harvard.edu/~elkies/FS23j.05/glossary_graph.html
  | work = Freshman Seminar 23j: Chess and Mathematics
  | publisher = Harvard University Mathematics Department
  | date = Fall 2004
  | authorlink = Noam Elkies | last = Elkies | first = Noam
  | access-date=2023-05-03}}.</ref>

<ref name=gm>{{citation
 | last1 = Gray | first1 = R.
 | last2 = Macpherson | first2 = D.
 | issue = 2
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 2595694
 | pages = 97–118
 | series = Series B
 | title = Countable connected-homogeneous graphs
 | volume = 100
 | year = 2010
 | doi=10.1016/j.jctb.2009.04.002| doi-access = free
 }}. See in particular Theorem 1, which identifies these graphs as line graphs of complete bipartite graphs.</ref>

<ref name=gs>{{citation
 | last1 = Goethals | first1 = J.-M.
 | last2 = Seidel | first2 = J. J.
 | doi = 10.4153/CJM-1970-067-9
 | journal = [[Canadian Journal of Mathematics]]
 | mr = 0282872
 | pages = 597–614
 | title = Strongly regular graphs derived from combinatorial designs
 | volume = 22
 | issue = 3
 | year = 1970| s2cid = 199082328
 | doi-access = free
 }}.</ref>

<ref name=harary>{{citation
 | last = Harary | first = Frank | authorlink = Frank Harary
 | journal = [[Pacific Journal of Mathematics]]
 | mr = 0103834
 | pages = 743–755
 | title = On the number of bi-colored graphs
 | url = http://projecteuclid.org/euclid.pjm/1103039700
 | volume = 8
 | issue = 4 | year = 1958
 | doi=10.2140/pjm.1958.8.743| doi-access = free
 }}. See in particular equation (10), p.&nbsp;748 for the automorphism group of the <math>n\times n</math> rook's graph, and the discussion above the equation for the order of this group.</ref>

<ref name=hm>{{citation
 | last1 = Herzberg | first1 = Agnes M. | author1-link = Agnes M. Herzberg
 | last2 = Murty | first2 = M. Ram | author2-link = M. Ram Murty
 | issue = 6
 | journal = [[Notices of the American Mathematical Society]]
 | mr = 2327972
 | pages = 708–717
 | title = Sudoku squares and chromatic polynomials
 | url = https://www.ams.org/notices/200706/tx070600708p.pdf
 | volume = 54
 | year = 2007}}</ref>

<ref name=ho>{{citation
 | last1 = Hurley | first1 = C. B.
 | last2 = Oldford | first2 = R. W.
 | date = February 2011
 | doi = 10.1007/s00180-011-0228-6
 | issue = 4
 | journal = Computational Statistics
 | pages = 585–612
 | title = Graphs as navigational infrastructure for high dimensional data spaces
 | volume = 26| s2cid = 54220980
 }}</ref>

<ref name=hoffman>{{citation
  | last = Hoffman | authorlink = Alan J. Hoffman
  | title = On the line graph of the complete bipartite graph
  | journal = [[Annals of Mathematical Statistics]]
  | volume = 35
  | issue = 2
  | pages = 883–885
  | year = 1964
  | doi = 10.1214/aoms/1177703593
  | mr = 0161328
  | first = A. J.| doi-access = free
  }}.</ref>

<ref name=lpp>For an equivalent statement to the well-covered property of rook's graphs, in terms of matchings in complete bipartite graphs, see {{citation
 | last1 = Lesk | first1 = M.
 | last2 = Plummer | first2 = M. D.
 | last3 = Pulleyblank | first3 = W. R.
 | editor-last = Bollobás | editor-first = Béla
 | contribution = Equi-matchable graphs
 | location = London
 | mr = 777180
 | pages = 239–254
 | publisher = Academic Press
 | title = Graph Theory and Combinatorics: Proceedings of the Cambridge Combinatorial Conference, in Honour of Paul Erdős
 | year = 1984}}.</ref>

<ref name=lsww>For the equivalence between edge-coloring complete bipartite graphs and Latin squares, see e.g. {{citation
 | last1 = LeSaulnier | first1 = Timothy D.
 | last2 = Stocker | first2 = Christopher
 | last3 = Wenger | first3 = Paul S.
 | last4 = West | first4 = Douglas B.
 | issue = 1
 | journal = [[Electronic Journal of Combinatorics]]
 | mr = 2651735
 | page = Note 26, 5
 | title = Rainbow matching in edge-colored graphs
 | url = http://www.combinatorics.org/Volume_17/Abstracts/v17i1n26.html
 | volume = 17
 | year = 2010 | doi = 10.37236/475| doi-access = free
 }}.</ref>

<ref name=lw>{{citation
 | last1 = Laskar | first1 = Renu | author1-link = Renu C. Laskar
 | last2 = Wallis | first2 = Charles
 | doi = 10.1016/S0378-3758(98)00132-3
 | issue = 1–2
 | journal = [[Journal of Statistical Planning and Inference]]
 | mr = 1673351
 | pages = 285–294
 | title = Chessboard graphs, related designs, and domination parameters
 | volume = 76
 | year = 1999}}.</ref>

<ref name=moon>{{citation
  | last = Moon | first = J. W.
  | title = On the line-graph of the complete bigraph
  | journal = [[Annals of Mathematical Statistics]]
  | volume = 34
  | issue = 2
  | year = 1963
  | pages = 664–667
  | doi = 10.1214/aoms/1177704179 | doi-access = free}}.</ref>

<ref name=mpp>{{citation
 | last1 = Matschke | first1 = Benjamin
 | last2 = Pfeifle | first2 = Julian
 | last3 = Pilaud | first3 = Vincent
 | arxiv = 0908.4177
 | doi = 10.1007/s00454-010-9311-y
 | issue = 1
 | journal = [[Discrete & Computational Geometry]]
 | mr = 2794360
 | pages = 100–131
 | title = Prodsimplicial-neighborly polytopes
 | volume = 46
 | year = 2011| s2cid = 2070310
 }}</ref>

<ref name=simploid>{{citation
 | last = Moore | first = Doug
 | editor-last = Kirk | editor-first = David
 | contribution = Understanding simploids
 | doi = 10.1016/b978-0-08-050755-2.50057-9
 | pages = 250–255
 | publisher = [[Academic Press]]
 | title = Graphics Gems III
 | year = 1992}}</ref>

<ref name=stone>{{citation
 | last = Stones | first = Douglas S.
 | doi = 10.37236/487 | doi-access = free
 | issue = 1
 | journal = Electronic Journal of Combinatorics
 | mr = 2661404
 | page = A1:1–A1:46
 | title = The many formulae for the number of Latin rectangles
 | volume = 17
 | year = 2010}}</ref>

<ref name=stones>{{citation
 | last = Stones | first = Douglas S.
 | doi = 10.37236/487
 | issue = 1
 | journal = Electronic Journal of Combinatorics
 | mr = 2661404
 | page = Article 1, 46
 | title = The many formulae for the number of Latin rectangles
 | url = https://www.combinatorics.org/Volume_17/Abstracts/v17i1a1.html
 | volume = 17
 | year = 2010| doi-access = free
 }}</ref>

<ref name=w>{{citation|title=Across the Board: The Mathematics of Chessboard Problems|first=John J.|last=Watkins|publisher=Princeton University Press|year=2004|isbn=9780691130620|page=[https://books.google.com/books?id=EQSPm1MPKJUC&pg=PA12 12]}}</ref>

<ref name=yy>{{citation
 | last1 = Yaglom | first1 = A. M. | author1-link = Akiva Yaglom
 | last2 = Yaglom | first2 = I. M. | author2-link = Isaak Yaglom
 | publisher = Dover
 | contribution = Solution to problem 34b
 | page = 77
 | url = https://books.google.com/books?id=VkHDAgAAQBAJ&pg=PA77
 | title = Challenging Mathematical Problems with Elementary Solutions
 | year = 1987| isbn = 9780486318578 }}.</ref>

}}

==External links==
*{{mathworld|title=Rook Graph|urlname=RookGraph|mode=cs2|ref=none}}

[[Category:Mathematical chess problems]]
[[Category:Perfect graphs]]
[[Category:Parametric families of graphs]]
[[Category:Regular graphs]]
[[Category:Strongly regular graphs]]