There are two conflicting definitions of the lattice graph. Ball and Coxeter (1987, p. 305) define a lattice graph as the graph obtained by taking the ordered pairs of the first positive integers as vertices and drawing an edge between all pairs having exactly one number in common. In this work, such a graph will be regarded as a generalized square graph.

The more usual definition of a lattice graph (confusingly called the grid by Brouwer et al. 1989, p. 440) is 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 form of lattice graph corresponds to a rook's tour graph on an chessboard, i.e., a tour by a chess piece that can move any number of spaces in a straight line (either horizontally or vertically, but not diagonally).

The lattice 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 lattice graph.

The lattice graph is also the graph complement of the crown graph on vertices. The lattice graph is isomorphic to the 25-cyclotomic graph.

Precomputed properties of lattice graphs are implemented in Mathematica as GraphData["Lattice", m, n].

A lattice graph is a circulant graph iff (i.e., is coprime to ). In that case, the lattice graph is isomorphic to .

Special cases are summarized in the following table.

	isomorphic to
	prism graph
	square graph
	circulant graph
	circulant graph

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, 1987.

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.

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.

van Dam, E. R. and Haemers, W. H. "Which Graphs Are Determined by Their Spectrum?" Lin. Algebra Appl. 373, 139-162, 2003.

CITE THIS AS:

Weisstein, Eric W. "Lattice Graph." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/LatticeGraph.html