Rook's graph

Last updated

Rook's graph
Rook's graph.svg
8x8 Rook's graph
Vertices
Edges
Diameter
Girth (if )
Chromatic number
Spectrum
Properties
Table of graphs and parameters

In graph theory, a rook's graph is an undirected 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 there is an 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 two complete graphs, and are the line graphs of complete bipartite graphs. The square rook's graphs constitute the two-dimensional Hamming graphs.

Contents

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). For rectangular chessboards whose width and height are relatively prime, the rook's graphs are circulant graphs. 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 4-cycle connecting each nonadjacent pair of vertices.

Rook's graphs are perfect graphs. In other words, every subset of chessboard squares can be 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 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 n × m rook's graph represents the moves of a rook on an n × m chessboard. [1] Its vertices represent the squares of the chessboard, and may be given coordinates (x, y), where 1 ≤ xn and 1 ≤ ym. Two vertices with coordinates (x1, y1) and (x2, y2) are adjacent if and only if either x1 = x2 or y1 = y2. (If x1 = x2, the vertices share a file and are connected by a vertical rook move; if y1 = y2, they share a rank and are connected by a horizontal rook move.) [1]

The squares of a single rank or file are all directly connected to each other, so each rank and file forms a clique—a subset of vertices forming a complete graph. The whole rook's graph for an n × m chessboard can be formed from these two kinds of cliques, as the Cartesian product of graphs KnKm. [2] 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. [3] 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. [4] The Sudoku graphs are rook's graphs with some additional edges, connecting squares of a Sudoku puzzle that should have unequal values. [5]

The 3-3 duoprism, a four-dimensional convex polytope having a 3 x 3 rook's graph as its skeleton Triangular Duoprism YW and ZW Rotations.gif
The 3-3 duoprism, a four-dimensional convex polytope having a 3 × 3 rook's graph as its skeleton

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

Regularity and symmetry

Strong regularity

Moon (1963) and Hoffman (1964) observe that the rook's graph (or equivalently, as they describe it, the line graph of the complete bipartite graph ) has all of the following properties:

They show that except in the case , 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. [8] [9]

When , these conditions may be abbreviated by stating that an rook's graph is a strongly regular graph with parameters . 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. [1] Conversely, every strongly regular graph with these parameters must be an rook's graph, unless . [8] [9]

The Shrikhande graph embedded on a torus. This is not a rook's graph, but is strongly regular with the same parameters as the
4
x
4
{\displaystyle 4\times 4}
rook's graph. Shrikhande torus.svg
The Shrikhande graph embedded on a torus. This is not a rook's graph, but is strongly regular with the same parameters as the rook's graph.

When , there is another strongly regular graph, the Shrikhande graph, with the same parameters as the rook's graph. [10] The Shrikhande graph obeys the same properties listed by Moon and Moser. It can be distinguished from the rook's graph in that the neighborhood of each vertex in the Shrikhande graph is connected to form a -cycle. In contrast, in the 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. [11] Another way of distinguishing the rook's graph from the Shrikhande graph uses clique cover numbers: the 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. [10]

Symmetry

Rook's graphs are 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 -regular. The rook's graphs are the only regular graphs formed from the moves of standard chess pieces in this way. [12] When , 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 elements. When , the graph has additional symmetries that swap the rows and columns, so the number of automorphisms is . [13]

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. [14]

When and are relatively prime, the symmetry group of the rook's graph contains as a subgroup the cyclic group that acts by cyclically permuting the vertices. Therefore, in this case, the rook's graph is a circulant graph. [15]

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. [16]

Other properties

Perfection

The 3x3 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. Paley9-perfect.svg
The 3×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 Kn,m — that is, it has one vertex for each edge of Kn,m, 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. [2] [17] In this view, an edge in the complete bipartite graph from the ith vertex on one side of the bipartition to the jth vertex on the other side corresponds to a chessboard square with coordinates (i, j). [1]

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. [18] 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 Chudnovsky et al. (2006) to characterize the perfect graphs and to show that every graph with no odd hole and no odd antihole is perfect. [19] In particular, rook's graphs are themselves perfect.

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

Independence

abcdefgh
8
Chessboard480.svg
Chess rlt45.svg
Chess rlt45.svg
Chess rlt45.svg
Chess rlt45.svg
Chess rlt45.svg
Chess rlt45.svg
Chess rlt45.svg
Chess rlt45.svg
8
77
66
55
44
33
22
11
abcdefgh
A non-attacking placement of eight rooks on a chessboard, forming a maximum independent set in the corresponding rook's graph

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 min(m, n). [1]

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, min(m, n). [23]

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 m×n board. For the m×n board the domination number is min(m, n). [24]

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

Hamiltonicity

Every rook's graph contains a Hamiltonian cycle. [26] 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. [27] They are featured alongside knight's tours in the first work to discuss chess-piece tours, the 9th century Sanskrit Kavyalankara of Rudrata. [28]

Spectrum

The spectrum of a rook's graph (the eigenvalues of its adjacency matrix) consists of the four eigenvalues , , , and . 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 ; one of the three classes is the class of rook's graphs. For most combinations of and , the rook's graph is spectrally unique: no other graph has the same spectrum. In particular this is true when or , or when the two numbers and sum to at least 18 and do not have the form . [29]

In other graphs

The graphs for which the neighbors of each vertex induce a rook's graph have been called locally grid. Examples include the Johnson graphs , for which the neighbors of each vertex form a 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 rook's graphs: they are the Johnson graph , and the complement graph of a rook's graph. [30]

See also

Related Research Articles

<span class="mw-page-title-main">Bipartite graph</span> Graph divided into two independent sets

In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets and , that is, every edge connects a vertex in to one in . Vertex sets and are usually called the parts of the graph. Equivalently, a bipartite graph is a graph that does not contain any odd-length cycles.

<span class="mw-page-title-main">Hamiltonian path</span> Path in a graph that visits each vertex exactly once

In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. The computational problems of determining whether such paths and cycles exist in graphs are NP-complete; see Hamiltonian path problem for details.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Clique (graph theory)</span> Adjacent subset of an undirected graph

In graph theory, a clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph is an induced subgraph of that is complete. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs. Cliques have also been studied in computer science: the task of finding whether there is a clique of a given size in a graph is NP-complete, but despite this hardness result, many algorithms for finding cliques have been studied.

<span class="mw-page-title-main">Complete bipartite graph</span> Bipartite graph where each node of 1st set is linked to all nodes of 2nd set

In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set.

In the mathematical field of graph theory, an edge-transitive graph is a graph G such that, given any two edges e1 and e2 of G, there is an automorphism of G that maps e1 to e2.

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

<span class="mw-page-title-main">Perfect graph theorem</span> An undirected graph is perfect if and only if its complement graph is also perfect

In graph theory, the perfect graph theorem of László Lovász states that an undirected graph is perfect if and only if its complement graph is also perfect. This result had been conjectured by Berge, and it is sometimes called the weak perfect graph theorem to distinguish it from the strong perfect graph theorem characterizing perfect graphs by their forbidden induced subgraphs.

In the mathematical discipline of graph theory, the line graph of an undirected graph G is another graph L(G) that represents the adjacencies between edges of G. L(G) is constructed in the following way: for each edge in G, make a vertex in L(G); for every two edges in G that have a vertex in common, make an edge between their corresponding vertices in L(G).

<span class="mw-page-title-main">Cograph</span> Graph formed by complementation and disjoint union

In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K1 and is closed under complementation and disjoint union.

<span class="mw-page-title-main">Kőnig's theorem (graph theory)</span> Theorem showing that maximum matching and minimum vertex cover are equivalent for bipartite graphs

In the mathematical area of graph theory, Kőnig's theorem, proved by Dénes Kőnig, describes an equivalence between the maximum matching problem and the minimum vertex cover problem in bipartite graphs. It was discovered independently, also in 1931, by Jenő Egerváry in the more general case of weighted graphs.

<span class="mw-page-title-main">Hypercube graph</span> Graphs formed by a hypercubes edges and vertices

In graph theory, the hypercube graphQn is the graph formed from the vertices and edges of an n-dimensional hypercube. For instance, the cube graph Q3 is the graph formed by the 8 vertices and 12 edges of a three-dimensional cube. Qn has 2n vertices, 2n – 1n edges, and is a regular graph with n edges touching each vertex.

<span class="mw-page-title-main">Neighbourhood (graph theory)</span> Subgraph made of all nodes linked to a given node of a graph

In graph theory, an adjacent vertex of a vertex v in a graph is a vertex that is connected to v by an edge. The neighbourhood of a vertex v in a graph G is the subgraph of G induced by all vertices adjacent to v, i.e., the graph composed of the vertices adjacent to v and all edges connecting vertices adjacent to v.

<span class="mw-page-title-main">Claw-free graph</span> Graph without four-vertex star subgraphs

In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw as an induced subgraph.

<span class="mw-page-title-main">Clique complex</span> Abstract simplicial complex describing a graphs cliques

Clique complexes, independence complexes, flag complexes, Whitney complexes and conformal hypergraphs are closely related mathematical objects in graph theory and geometric topology that each describe the cliques of an undirected graph.

<span class="mw-page-title-main">Well-covered graph</span> Graph with equal-size maximal independent sets

In graph theory, a well-covered graph is an undirected graph in which the minimal vertex covers all have the same size. Here, a vertex cover is a set of vertices that touches all edges, and it is minimal if removing any vertex from it would leave some edge uncovered. Equivalently, well-covered graphs are the graphs in which all maximal independent sets have equal size. Well-covered graphs were defined and first studied by Michael D. Plummer in 1970.

<span class="mw-page-title-main">Skew partition</span>

In graph theory, a skew partition of a graph is a partition of its vertices into two subsets, such that the induced subgraph formed by one of the two subsets is disconnected and the induced subgraph formed by the other subset is the complement of a disconnected graph. Skew partitions play an important role in the theory of perfect graphs.

<span class="mw-page-title-main">Map graph</span> Intersection graph representing regions on the Euclidean plane

In graph theory, a branch of mathematics, a map graph is an undirected graph formed as the intersection graph of finitely many simply connected and internally disjoint regions of the Euclidean plane. The map graphs include the planar graphs, but are more general. Any number of regions can meet at a common corner, and when they do the map graph will contain a clique connecting the corresponding vertices, unlike planar graphs in which the largest cliques have only four vertices. Another example of a map graph is the king's graph, a map graph of the squares of the chessboard connecting pairs of squares between which the chess king can move.

The independence complex of a graph is a mathematical object describing the independent sets of the graph. Formally, the independence complex of an undirected graph G, denoted by I(G), is an abstract simplicial complex (that is, a family of finite sets closed under the operation of taking subsets), formed by the sets of vertices in the independent sets of G. Any subset of an independent set is itself an independent set, so I(G) is indeed closed under taking subsets.

In mathematics, a queen's graph is an undirected graph that represents all legal moves of the queen—a chess piece—on a chessboard. In the graph, each vertex represents a square on a chessboard, and each edge is a legal move the queen can make, that is, a horizontal, vertical or diagonal move by any number of squares. If the chessboard has dimensions , then the induced graph is called the queen's graph.

References

  1. 1 2 3 4 5 Laskar, Renu; Wallis, Charles (1999), "Chessboard graphs, related designs, and domination parameters", Journal of Statistical Planning and Inference , 76 (1–2): 285–294, doi:10.1016/S0378-3758(98)00132-3, MR   1673351 .
  2. 1 2 Stones, Douglas S. (2010), "The many formulae for the number of Latin rectangles", Electronic Journal of Combinatorics, 17 (1): Article 1, 46, doi: 10.37236/487 , MR   2661404
  3. Azizoğlu, M. Cemil; Eğecioğlu, Ömer (2003), "Extremal sets minimizing dimension-normalized boundary in Hamming graphs", SIAM Journal on Discrete Mathematics , 17 (2): 219–236, doi:10.1137/S0895480100375053, MR   2032290 .
  4. Goethals, J.-M.; Seidel, J. J. (1970), "Strongly regular graphs derived from combinatorial designs", Canadian Journal of Mathematics , 22 (3): 597–614, doi: 10.4153/CJM-1970-067-9 , MR   0282872, S2CID   199082328 .
  5. Herzberg, Agnes M.; Murty, M. Ram (2007), "Sudoku squares and chromatic polynomials" (PDF), Notices of the American Mathematical Society , 54 (6): 708–717, MR   2327972
  6. Matschke, Benjamin; Pfeifle, Julian; Pilaud, Vincent (2011), "Prodsimplicial-neighborly polytopes", Discrete & Computational Geometry , 46 (1): 100–131, arXiv: 0908.4177 , doi:10.1007/s00454-010-9311-y, MR   2794360, S2CID   2070310
  7. Moore, Doug (1992), "Understanding simploids", in Kirk, David (ed.), Graphics Gems III, Academic Press, pp. 250–255, doi:10.1016/b978-0-08-050755-2.50057-9
  8. 1 2 Moon, J. W. (1963), "On the line-graph of the complete bigraph", Annals of Mathematical Statistics , 34 (2): 664–667, doi: 10.1214/aoms/1177704179 .
  9. 1 2 Hoffman, A. J. (1964), "On the line graph of the complete bipartite graph", Annals of Mathematical Statistics , 35 (2): 883–885, doi: 10.1214/aoms/1177703593 , MR   0161328 .
  10. 1 2 Fiala, Nick C.; Haemers, Willem H. (2006), "5-chromatic strongly regular graphs", Discrete Mathematics , 306 (23): 3083–3096, doi: 10.1016/j.disc.2004.03.023 , MR   2273138 .
  11. Burichenko, V. P.; Makhnev, A. A. (2011), "Об автоморфизмах сильно регулярных локально циклических графов" [On automorphisms of strongly regular locally cyclic graphs], Doklady Akademii Nauk (in Russian), 441 (2): 151–155, MR   2953786 . 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)."
  12. Elkies, Noam (Fall 2004), "Graph theory glossary", Freshman Seminar 23j: Chess and Mathematics, Harvard University Mathematics Department, retrieved 2023-05-03.
  13. Harary, Frank (1958), "On the number of bi-colored graphs", Pacific Journal of Mathematics , 8 (4): 743–755, doi: 10.2140/pjm.1958.8.743 , MR   0103834 . See in particular equation (10), p. 748 for the automorphism group of the rook's graph, and the discussion above the equation for the order of this group.
  14. Biggs, Norman (1974), "The symmetry of line graphs", Utilitas Mathematica, 5: 113–121, MR   0347684 .
  15. This follows from the definition of the rook's graph as a Cartesian product graph, together with Proposition 4 of Broere, Izak; Hattingh, Johannes H. (1990), "Products of circulant graphs", Quaestiones Mathematicae, 13 (2): 191–216, doi:10.1080/16073606.1990.9631612, MR   1068710 .
  16. Gray, R.; Macpherson, D. (2010), "Countable connected-homogeneous graphs", Journal of Combinatorial Theory , Series B, 100 (2): 97–118, doi: 10.1016/j.jctb.2009.04.002 , MR   2595694 . See in particular Theorem 1, which identifies these graphs as line graphs of complete bipartite graphs.
  17. For the equivalence between Cartesian products of complete graphs and line graphs of complete bipartite graphs, see de Werra, D.; Hertz, A. (1999), "On perfectness of sums of graphs" (PDF), Discrete Mathematics , 195 (1–3): 93–101, doi: 10.1016/S0012-365X(98)00168-X , MR   1663807 .
  18. de Werra & Hertz (1999).
  19. Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), "The strong perfect graph theorem" (PDF), Annals of Mathematics , 164 (1): 51–229, arXiv: math/0212070 , doi:10.4007/annals.2006.164.51, JSTOR   20159988, S2CID   119151552 .
  20. For the equivalence between edge-coloring complete bipartite graphs and Latin squares, see e.g. LeSaulnier, Timothy D.; Stocker, Christopher; Wenger, Paul S.; West, Douglas B. (2010), "Rainbow matching in edge-colored graphs", Electronic Journal of Combinatorics , 17 (1): Note 26, 5, doi: 10.37236/475 , MR   2651735 .
  21. Stones, Douglas S. (2010), "The many formulae for the number of Latin rectangles", Electronic Journal of Combinatorics, 17 (1): A1:1–A1:46, doi: 10.37236/487 , MR   2661404
  22. Colbourn, Charles J. (1984), "The complexity of completing partial Latin squares", Discrete Applied Mathematics , 8 (1): 25–30, doi: 10.1016/0166-218X(84)90075-1 , MR   0739595 .
  23. For an equivalent statement to the well-covered property of rook's graphs, in terms of matchings in complete bipartite graphs, see Lesk, M.; Plummer, M. D.; Pulleyblank, W. R. (1984), "Equi-matchable graphs", in Bollobás, Béla (ed.), Graph Theory and Combinatorics: Proceedings of the Cambridge Combinatorial Conference, in Honour of Paul Erdős, London: Academic Press, pp. 239–254, MR   0777180 .
  24. Yaglom, A. M.; Yaglom, I. M. (1987), "Solution to problem 34b", Challenging Mathematical Problems with Elementary Solutions, Dover, p. 77, ISBN   9780486318578 .
  25. Burchett, Paul; Lane, David; Lachniet, Jason (2009), "K-domination and k-tuple domination on the rook's graph and other results", Congressus Numerantium, 199: 187–204.
  26. Hurley, C. B.; Oldford, R. W. (February 2011), "Graphs as navigational infrastructure for high dimensional data spaces", Computational Statistics, 26 (4): 585–612, doi:10.1007/s00180-011-0228-6, S2CID   54220980
  27. Watkins, John J. (2004), Across the Board: The Mathematics of Chessboard Problems, Princeton University Press, p.  12, ISBN   9780691130620
  28. Murray, H. J. R. (January 1902), "The knight's tour: ancient and oriental", The British Chess Magazine, vol. 22, no. 1, pp. 1–7
  29. Doob, Michael (1970), "On characterizing certain graphs with four eigenvalues by their spectra", Linear Algebra and Its Applications , 3 (4): 461–482, doi: 10.1016/0024-3795(70)90037-6 , MR   0285432
  30. Cohen, Arjeh M. (1990), "Local recognition of graphs, buildings, and related geometries" (PDF), in Kantor, William M.; Liebler, Robert A.; Payne, Stanley E.; Shult, Ernest E. (eds.), Finite Geometries, Buildings, and Related Topics: Papers from the Conference on Buildings and Related Geometries held in Pingree Park, Colorado, July 17–23, 1988, Oxford Science Publications, Oxford University Press, pp. 85–94, MR   1072157 ; see in particular pp. 89–90