# 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, perfectIngraph theory , a**rook's graph**(also called a**lattice graph**) is a graph that represents all legal moves of the rookchess piece on achessboard : each vertex represents a square on a chessboard and each edge represents a legal move. Rook's graphs are highly symmetricperfect graph s; 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"

_{1},"y"_{1}) and ("x"_{2},"y"_{2}) are connected by an edge if and only if either "x"_{1}= "x"_{2}or "y"_{1}= "y"_{2}; 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 aLatin square graph.The rook's graph for an "n"×"m" chessboard may also be defined as the Cartesian product of two

complete graph s "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 thecyclic group "C_{mn}" = "C_{m}"×"C_{n}" that acts by cyclically permuting the "mn" vertices; therefore, in this case, the rook's graph is acirculant graph .**Perfection**A rook's graph can also be viewed as the

line graph of acomplete 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 asubgraph of a complete bipartite graph, and correspondingly any line graph of a bipartite graph is aninduced 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 astrongly regular graph with parameterssrg("n"^{2}, 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 = Bekmetjev | first1 = Airat | last2 = Hurlbert | first2 = Glenn

title = The pebbling threshold of the square of cliques

id = arxiv|archive = math.CO|id = 0406157

year = 2004.*citation

last1 = Berger-Wolf | first1 = Tanya Y. | last2 = Harris | first2 = Mitchell A.

title = Sharp bounds for bandwidth of clique products

id = arxiv|archive = cs.DM|id = 0305051

year = 2003.*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

title = The second largest component in the supercritical 2D Hamming graph

first1 = Malwina J. | last1 = Luczak | first2 = Joel | last2 = Spencer | authorlink2 = Joel Spencer

year = 2008

id = arxiv | 0801.1608.*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