Rook's graph

infobox graph
name = Rook's graph

image_caption = 8x8 Rook's graph
vertices = "nm"
edges = "nm"("n"+"m")/2 - "nm"
diameter = 2
chromatic_number = max("n","m")
chromatic_index =
girth = 3 (if max("n","m") ≥ 3)
properties = regular, vertex-transitive, perfectIn graph theory, a rook's graph (also called a lattice graph) is a graph that represents all legal moves of the rook chess piece on a chessboard: each vertex represents a square on a chessboard and each edge represents a legal move. Rook's graphs are highly symmetric perfect graphs; they may be characterized in terms of the the number of triangles each edge belongs to and by the existence of a 4-cycle connecting each nonadjacent pair of vertices.

Definitions

An "n"×"m" rook's graph represents the moves of a rook on an "n"×"m" chessboard.Its vertices may be given coordinates ("x","y"), where 1 ≤ "x" ≤ "n" and 1 ≤ "y" ≤ "m". Two vertices ("x"₁,"y"₁) and ("x"₂,"y"₂) are connected by an edge if and only if either "x"₁ = "x"₂ or "y"₁ = "y"₂; that is, if they belong to the same row or the same column of the chessboard.

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

The rook's graph for an "n"×"m" chessboard may also be defined as the Cartesian product of two complete graphs "K"_"n" $square$ "K"_"m".

ymmetry

Rook's graphs are vertex-transitive and ("n" + "m" − 2)-regular; they are the only regular graphs formed from the moves of standard chess pieces in this way (Elkies). When "m" ≠ "n", the symmetries of the rook's graph are formed by independently permuting the rows and columns of the graph. When "n" = "m" the graph has additional symmetries that swap the rows and columns; the rook's graph for a square chessboard is symmetric.

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.

When "m" and "n" are relatively prime, the symmetry group "S_m"×"S_n" of the rook's graph contains as a subgroup the cyclic group "C_mn" = "C_m"×"C_n" that acts by cyclically permuting the "mn" vertices; therefore, in this case, the rook's graph is a circulant graph.

Perfection

A rook's graph can also be viewed as the line graph of a complete bipartite graph "K"_"n","m" — that is, it has one vertex for each edge of "K"_"n","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. In this view, an edge in the complete bipartite graph from the "i"th vertex on one side of the bipartition to the "j"th vertex on the other side corresponds to a chessboard square with coordinates ("i","j").

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

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. 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"). Every color class in every optimal coloring of a rook's graph is a maximum independent set.

Characterization

harvtxt|Moon|1963 characterizes the "m" × "n" rook's graph as the unique graph having the following properties:

*It has "mn" vertices, each of which is adjacent to "n" + "m" − 2 edges.
*"mn"("m" −1)/2 of the edges belong to "m" − 2 triangles and the remaining "mn"("n" −1)/2 edges belong to "n" − 2 triangles.
*Any two vertices that are not adjacent to each other belong to a unique 4-cycle.When "n" = "m", these conditions may be abbreviated by stating that an "n"×"n" rook's graph is a strongly regular graph with parameterssrg("n"², 2"n" − 2, "n" − 2, 2), and that every strongly regular graph with these parameters must be an "n"×"n" rook's graph.

See also

* King's graph
* Knight's graph

References

*citation
last = Beka | first Ján
title = "K"_"n"-decomposition of the line graphs of complete bipartite graphs
journal = Octogon Mathematical Magazine
volume = 9
issue = 1A
year = 2001
pages = 135–139.

*citation
last1 = Chudnovsky | first1 = Maria
authorlink2 = Neil Robertson (mathematician)| last2 = Robertson | first2 = Neil
authorlink3 = Paul Seymour (mathematician) | last3 = Seymour | first3 = Paul
last4 = Thomas | first4 = Robin
year = 2006
url = http://annals.math.princeton.edu/issues/2006/July2006/ChudnovskyRobertsonSeymourThomas.pdf
title = The strong perfect graph theorem
journal = Annals of Mathematics
volume = 164
pages = 51–229.

*citation
title = Graph theory glossary
url = http://www.math.harvard.edu/~elkies/FS23j.05/glossary_graph.html
authorlink = Noam Elkies | last = Elkies | first = Noam.

*citation
last = Hoffman | first A. J.
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.

*citation
title = Random subgraphs of the 2D Hamming graph: the supercritical phase
first1 = Remco | last1 = van der Hofstad | first2 = Malwina J. | last2 = Luczak
year = 2008
id = arxiv | 0801.1607.

*citation
last1 = Laskar | first1 = Renu | last2 = Wallis | first2 = Charles
title = Chessboard graphs, related designs, and domination parameters
journal = Journal of Statistical Planning and Inference
volume = 76
issue = 1–2
pages = 285–294
year = 1999
doi = 10.1016/S0378-3758(98)00132-3.

*citation
last1 = MacGillivray | first1 = G. | last2 = Seyffarth | first2 = K.
title = Classes of line graphs with small cycle double covers
journal = Australasian Journal of Combinatorics
volume = 24
year = 2001
pages = 91–114.

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

*citation
last1 = de Werra | first1 = D. | last2 = Hertz | first2 = A.
title = On perfectness of sums of graphs
journal = Discrete Mathematics
volume = 195
year = 1999
pages = 93–101
url = http://www.gerad.ca/~alainh/Sum.pdf
doi = 10.1016/S0012-365X(98)00168-X.

External links

*mathworld|title=Lattice Graph|urlname=LatticeGraph

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

Rook — may refer to:Bird*Rook (bird), a member of the passerine order of birds and the crow familyGames*Rook (chess), a piece in the board game of chess **Rook and pawn versus rook endgame, chess endgame **Rook s graph, a graph that represents all legal … Wikipedia
Rook polynomial — Despite its name, the rook polynomial is used not only to solve chess recreational problems but also in a number of problems arising in combinatorial mathematics, group theory, and number theory.The coefficients of the rook polynomial represent… … Wikipedia
Circulant graph — The Paley graph of order 13, an example of a circulant graph. Crown graphs … Wikipedia
Lattice graph — The terms lattice graph, mesh graph, or grid graph refer to a number of categories of graphs whose drawing corresponds to some grid/mesh/lattice, i.e., its vertices correspond to the nodes of the mesh and its edges correspond to the ties between… … Wikipedia
Crown graph — Crown graphs with six, eight, and ten vertices. In graph theory, a branch of mathematics, a crown graph on 2n vertices is an undirected graph with two sets of vertices ui and vi and with an edge from ui to vj whenever i ≠ j. The crown… … Wikipedia
Strongly regular graph — Let G = (V,E) be a regular graph with v vertices and degree k . G is said to be strongly regular if there are also integers λ and μ such that:* Every two adjacent vertices have λ common neighbours.* Every two non adjacent vertices have μ common… … Wikipedia
Knight's graph — infobox graph name = Knight s graph image caption = 8x8 Knight s graph vertices = nm edges = 4 mn 6( m + n )+8 chromatic number = chromatic index = girth = 4 (if n ≥3, m ≥ 5) properties = In graph theory, a knight s tour graph is a graph that… … Wikipedia
King's graph — infobox graph name = King s graph image caption = 8x8 King s graph vertices = nm edges = 4 nm 3( n + m )+2 chromatic number = chromatic index = girth = properties = In graph theory, a king s graph is a graph that represents all legal moves of the … Wikipedia
Hamming graph — Hamming graphs are a special class of graphs used in several branches of mathematics and computer science. Let S be a set of q elements and d a positive integer. The Hamming graph H ( d , q ) has vertex set Sd , the set of ordered d tuples of… … Wikipedia
Line graph — This article is about the mathematical concept. For statistical presentation method, see line chart. In graph theory, the line graph L(G) of undirected graph G is another graph L(G) that represents the adjacencies between edges of G. The name… … Wikipedia

Academic Dictionaries and Encyclopedias

Rook's graph

Look at other dictionaries:

Share the article and excerpts

Academic Dictionaries and Encyclopedias

Wikipedia

Rook's graph

Look at other dictionaries:

Share the article and excerpts

Direct link