Rook's graph
Rook's graph | ||
---|---|---|
Chromatic number max(n, m) | | |
Spectrum | {m + n − 2, m − 2, n − 2, −2} | |
Properties | ||
Table of graphs and parameters |
In
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
Rook's graphs are
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 ≤ x ≤ n and 1 ≤ y ≤ m. 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 Kn ◻ Km.[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]
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:
- It has vertices, one for each square of the chessboard. Each vertex is adjacent to edges, connecting it to the squares on the same rank and the 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 , exactly edges (the ones connecting squares on the same rank) belong to triangles; the remaining edges (the ones connecting squares on the same file) belong to triangles. When , each edge belongs to triangles.
- Every two nonadjacent vertices belong to a unique -vertex cycle, namely the only rectangle using the two vertices as corners.
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]
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
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
When and are
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
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.
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
Independence
a | b | c | d | e | f | g | h | ||
8 | 8 | ||||||||
7 | 7 | ||||||||
6 | 6 | ||||||||
5 | 5 | ||||||||
4 | 4 | ||||||||
3 | 3 | ||||||||
2 | 2 | ||||||||
1 | 1 | ||||||||
a | b | c | d | e | f | g | h |
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
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
Spectrum
The
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
- Chessboard complex, the independence complex of the rook's graph
- 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
- ^ MR 1673351.
- ^ MR 2661404
- MR 2032290.
- S2CID 199082328.
- MR 2327972
- S2CID 2070310
- ^ .
- ^ MR 0161328.
- ^ MR 2273138.
- . From the first page of the translation: "The Shrikhande graph is the only strongly regular locally hexagonal graph with parameters (16, 6, 2, 2)."
- ^ Elkies, Noam (Fall 2004), "Graph theory glossary", Freshman Seminar 23j: Chess and Mathematics, Harvard University Mathematics Department, retrieved 2023-05-03.
- 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.
- MR 0347684.
- MR 1068710.
- MR 2595694. See in particular Theorem 1, which identifies these graphs as line graphs of complete bipartite graphs.
- MR 1663807.
- ^ de Werra & Hertz (1999).
- S2CID 119151552.
- MR 2651735.
- MR 2661404
- MR 0739595.
- MR 0777180.
- ISBN 9780486318578.
- ^ 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.
- S2CID 54220980
- ISBN 9780691130620
- ^ Murray, H. J. R. (January 1902), "The knight's tour: ancient and oriental", The British Chess Magazine, vol. 22, no. 1, pp. 1–7
- MR 0285432
- MR 1072157; see in particular pp. 89–90