Rook's graph

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Rook's graph
Rook's graph.svg
8x8 Rook's graph
Vertices nm
Edges nm(n + m)/2 − nm
Diameter 2
Girth 3 (if max(n, m) ≥ 3)
Chromatic number max(n, m)
Properties regular,
vertex-transitive,
perfect
well-covered

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 represents a legal move from one square to another. The same graphs can be defined mathematically as the Cartesian products of two complete graphs or as the line graphs of complete bipartite graphs.

Rook's graphs are highly symmetric. For square chessboards they are distance-transitive graphs and distance-regular graphs, while for rectangular chessboards with relatively prime dimensions they are circulant graphs. They may be characterized in terms of the number of triangles each edge belongs to and by the existence of a 4-cycle connecting each nonadjacent pair of vertices.

Rook's graphs are perfect graphs, meaning that their induced subgraphs (the line graphs of bipartite graphs) all have chromatic number equal to their clique number. The induced subgraphs of rook's graphs 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 both equal the smaller of its two dimensions, and these are well-covered graphs meaning that every independent set can be extended to a maximum independent set.

Definition[edit]

An n × m rook's graph represents the moves of a rook on an n × m chessboard.[1] Its vertices may be given coordinates (x, y), where 1 ≤ xn and 1 ≤ ym. Two vertices (x1, y1) and (x2,y2) are adjacent if and only if either x1 = x2 or y1 = y2; that is, if they belong to the same rank or the same file of the chessboard.[1]

For an n × m rook's graph the total number of vertices is simply nm. For an n × n rook's graph the total number of vertices is simply n2 and the total number of edges is n3n2; in this case the graph is also known as a two-dimensional Hamming graph[2] or a Latin square graph.[3]

The rook's graph for an n × m chessboard may also be defined as the Cartesian product of two complete graphs Kn and Km, expressed in a single formula as KnKm. The complement graph of a 2 × n rook's graph is a crown graph.

Strong regularity[edit]

Moon (1963) and Hoffman (1964) observe that the rook's graph has all of the following properties:

  • It has vertices, each of which is adjacent to edges.
  • When , exactly edges belong to triangles and the remaining edges belong to triangles. When , each edge belongs to triangles.
  • Every two vertices that are not adjacent to each other belong to a unique -vertex cycle.

As they show, except in the case , these properties uniquely characterize the rook's graph. That is, the rook's graphs are the only graphs obeying all of these properties.[4][5]

When , these conditions may be abbreviated by stating that an rook's graph is a strongly regular graph with parameters .[1] Conversely, every strongly regular graph with these parameters must be an rook's graph, unless .[4][5]

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.[6] 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, disconnected from each other.[7] Alternatively, they may be distinguished by their clique cover numbers: the rook's graph can be covered by four cliques (the four rows or the four columns of the graph) whereas six cliques are needed to cover the Shrikhande graph.[6]

Symmetry[edit]

Rook's graphs are vertex-transitive and -regular; they are the only regular graphs formed from the moves of standard chess pieces in this way.[8] 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 .[9]

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

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

Perfection[edit]

The 3×3 rook's graph, 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.[12] 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.[13] 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.[14] 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 its rows and columns, 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.[15] 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.[16]

Independence[edit]

a b c d e f g h
8
Chessboard480.svg
d8 white rook
g7 white rook
c6 white rook
a5 white rook
b4 white rook
h3 white rook
e2 white rook
f1 white rook
8
7 7
6 6
5 5
4 4
3 3
2 2
1 1
a b c d e f g h
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] 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, min(m, n).[17]

Domination[edit]

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).[18]

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

See also[edit]

  • 3-3 duoprism, a 4-dimensional polytope having the rook's graph as the graph of its vertices and edges
  • King's graph and Knight's graph, two other graphs defined from the moves of chess pieces
  • Lattice graph, the graph of horizontal and vertical adjacencies of squares on a chessboard

References[edit]

  1. ^ a b c d e Laskar, Renu; Wallis, Charles (1999), "Chessboard graphs, related designs, and domination parameters", Journal of Statistical Planning and Inference, 76 (1-2): 285–294, MR 1673351, doi:10.1016/S0378-3758(98)00132-3 .
  2. ^ 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, MR 2032290, doi:10.1137/S0895480100375053 .
  3. ^ Goethals, J.-M.; Seidel, J. J. (1970), "Strongly regular graphs derived from combinatorial designs", Canadian Journal of Mathematics, 22: 597–614, MR 0282872, doi:10.4153/CJM-1970-067-9 .
  4. ^ a b 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 .
  5. ^ a b Hoffman, A. J. (1964), "On the line graph of the complete bipartite graph", Annals of Mathematical Statistics, 35 (2): 883–885, MR 0161328, doi:10.1214/aoms/1177703593 .
  6. ^ a b Fiala, Nick C.; Haemers, Willem H. (2006), "5-chromatic strongly regular graphs", Discrete Mathematics, 306 (23): 3083–3096, MR 2273138, doi:10.1016/j.disc.2004.03.023 .
  7. ^ 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)."
  8. ^ Elkies, Noam, Graph theory glossary .
  9. ^ Harary, Frank (1958), "On the number of bi-colored graphs", Pacific Journal of Mathematics, 8: 743–755, 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.
  10. ^ Biggs, Norman (1974), "The symmetry of line graphs", Utilitas Mathematica, 5: 113–121, MR 0347684 .
  11. ^ 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, MR 1068710, doi:10.1080/16073606.1990.9631612 .
  12. ^ 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, MR 1663807, doi:10.1016/S0012-365X(98)00168-X .
  13. ^ de Werra & Hertz (1999).
  14. ^ Chudnovsky, Maria; Robertson, Neil; Seymour, Paul; Thomas, Robin (2006), "The strong perfect graph theorem" (PDF), Annals of Mathematics, 164 (1): 51–229, JSTOR 20159988, doi:10.4007/annals.2006.164.51 .
  15. ^ 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, MR 2651735 .
  16. ^ Colbourn, Charles J. (1984), "The complexity of completing partial Latin squares", Discrete Applied Mathematics, 8 (1): 25–30, MR 739595, doi:10.1016/0166-218X(84)90075-1 .
  17. ^ For an equivalent statement to the well-covered property of rook's graphs, in terms of matchings in complete bipartite graphs, see Sumner, David P. (1979), "Randomly matchable graphs", Journal of Graph Theory, 3 (2): 183–186, MR 530304, doi:10.1002/jgt.3190030209 .
  18. ^ Yaglom, A. M.; Yaglom, I. M. (1987), "Solution to problem 34b", Challenging Mathematical Problems with Elementary Solutions, Dover, p. 77 .
  19. ^ 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 .

External links[edit]