Rook Graph
المؤلف:
Aubert, J. and Schneider, B.
المصدر:
"Décomposition de la somme cartésienne dun cycle et de lunion de deux cycles hamiltoniens en cycles hamiltoniens." Disc. Math. 38
الجزء والصفحة:
...
3-3-2022
3341
Rook Graph
The 
rook graph (confusingly called the 
grid by Brouwer et al. 1989, p. 440) and also sometimes known as a lattice graph (e.g., Brouwer) is the graph Cartesian product 
of complete graphs, which is equivalent to the line graph 
of the complete bipartite graph 
. This is the definition adopted for example by Brualdi and Ryser (1991, p. 153), although restricted to the case 
. This definition corresponds to the connectivity graph of a rook chess piece (which can move any number of spaces in a straight line-either horizontally or vertically, but not diagonally) on an 
chessboard.
The graph 
has 
vertices and 
edges. It is regular of degree 
, has diameter 3, girth 3 (for 
), and chromatic number 
. It is also perfect (since it is the line graph of a bipartite graph) and vertex-transitive.
The 
rook graph 
is also isomorphic to the Latin square graph. The vertices of such a graph are defined as the 
elements of a Latin square of order 
, with two vertices being adjacent if they lie in the same row or column or contain the same symbol. It turns out that all Latin squares of order 
produce the same rook graph.
Precomputed properties of rook graphs are implemented in the Wolfram Language as GraphData[![<span style=]()
{" src="https://mathworld.wolfram.com/images/equations/RookGraph/Inline19.svg" style="height:22px; width:6px" />"Rook", ![<span style=]()
{" src="https://mathworld.wolfram.com/images/equations/RookGraph/Inline20.svg" style="height:22px; width:6px" />m, n![<span style=]()
}" src="https://mathworld.wolfram.com/images/equations/RookGraph/Inline21.svg" style="height:22px; width:6px" />![<span style=]()
}" src="https://mathworld.wolfram.com/images/equations/RookGraph/Inline22.svg" style="height:22px; width:6px" />].
A rook graph 
is a circulant graph iff 
(i.e., 
is relatively prime to 
). In that case, the rook graph is isomorphic to 
.
Special cases are summarized in the following table.
 |
isomorphic to |
 |
square graph  |
 |
prism graph  |
 |
circulant graph  |
 |
graph complement of the  -crown graph |
 |
generalized quadrangle  |
 |
circulant graph  |
 |
25-cyclotomic graph |
The following table summarized the bipartite double graphs of the rook graph 
for small 
.
 |
bipartite double graph of  |
| 2 |
 |
| 3 |
tesseract graph  |
| 4 |
prism graph  |
| 5 |
Kummer graph |
| 5 |
Haar graph  |
A closed formula for the number of 7-cycles of 
is given by
(Perepechko and Voropaev).
The 
rook graph has domination number 
.
Aubert and Schneider (1982) showed that rook graphs admit Hamiltonian decomposition, meaning they are class 1 when they have even vertex count and class 2 when they have odd vertex count (because they are odd regular).
REFERENCES
Aubert, J. and Schneider, B. "Décomposition de la somme cartésienne d'un cycle et de l'union de deux cycles hamiltoniens en cycles hamiltoniens." Disc. Math. 38, 7-16, 1982.
Brouwer, A. E. "Lattice Graphs." http://www.win.tue.nl/~aeb/drg/graphs/Hamming.html.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.
Brouwer, A. E. and van Lint, J. H. "Strongly Regular Graphs and Partial Geometries." In Enumeration and Design: Papers from the conference on combinatorics held at the University of Waterloo, Waterloo, Ont., June 14-July 2, 1982 (Ed. D. M. Jackson and S. A. Vanstone). Toronto, Canada: Academic Press, pp. 85-122, 1984.
Brualdi, R. and Ryser, H. J. §6.2.4 in Combinatorial Matrix Theory. New York: Cambridge University Press, p. 152, 1991.
Godsil, C. and Royle, G. "Latin Square Graphs." §10.4 Algebraic Graph Theory. New York: Springer-Verlag, pp. 226-230, 2001.
Karavaev, A. M. "FlowProblem: Statistics of Simple Cycles." http://flowproblem.ru/paths/statistics-of-simple-cycles.Perepechko, S. N. and Voropaev, A. N. "The Number of Fixed Length Cycles in an Undirected Graph. Explicit Formulae in Case of Small Lengths."van Dam, E. R. and Haemers, W. H. "Which Graphs Are Determined by Their Spectrum?" Lin. Algebra Appl. 373, 139-162, 2003.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
