A two-dimensional grid graph, also known as a rectangular grid graph or two-dimensional lattice graph (e.g., Acharya and Gill 1981), is an 
lattice graph that
is the graph Cartesian product 
of path graphs
on 
and 
vertices. The 
grid graph is sometimes denoted 
(e.g., Acharya and Gill 1981). The particular case of
an 
rectangular grid graph is sometimes
known as a square grid graph.
Unfortunately, the convention concerning which index corresponds to width and which to height remains murky. Some authors (e.g., Acharya and Gill 1981) use the same
height by width convention applied to matrix dimensioning
(which also corresponds to the order in which measurements of a painting on canvas
are expressed). The Wolfram Language
implementation GridGraph[
m, n, ...
] also adopts this ordering, returning an embedding in which
corresponds to the height and 
the width. Other sources adopt the "width by height"'
convention used to measure paper, room dimensions, and windows (e.g., 8 1/2 inch
by 11 inch paper is 8 1/2 inches wide and 11 inches high). Therefore, depending on
convention, the graph illustrated above may be referred to either as the 
grid graph or the 
grid graph.
Yet another convention wrinkle is used by Harary (1994, p. 194), who does not explciitly state which index corresponds to which dimension, but uses a 0-offset
numbering in defining a 2-lattice as a graph whose points are ordered pairs of integers
with 
, 1, ..., 
and 
,
1, ..., 
.
If Harary's ordered pairs are interpreted as Cartesian coordinates, a grid graph
with parameters 
and 
consists of 
vertices along the 
-axis and 
along the 
-axis. This is consistent with the interpretaion of 
in the graph
Cartesian product as paths with 
and 
edges
(and hence 
and 
vertices), respectively.
Note that Brouwer et al. (1989, p. 440) use the term "
grid" to refer to the line
graph 
of the complete bipartite graph 
, known in this work as the rook
graph 
.
Precomputed properties for a number of grid graphs are available using GraphData[
"Grid", 
m, ..., r, ...
].
A grid graph 
has 
vertices and 
edges.
A grid graph 
is Hamiltonian if either the number of rows
or columns is even (Skiena 1990, p. 148). Grid graphs are also bipartite (Skiena
1990, p. 148). 
and 
grid graphs are graceful
(Acharya and Gill 1981, Gallian 2018).
-dimensional grid graphs of arbitrary
dimension and shape appear to be traceable, though
a proof of this assertion in its entirely does not seem to appear in the literature
(cf. Simmons 1978, Hedetniemi et al. 1980, Itai et al. 1982, Zamfirescu
and Zamfirescu 1992).
The numbers of directed Hamiltonian paths on the 
grid graph for 
, 2, ... are given by 1, 8, 40, 552, 8648, 458696, 27070560,
... (OEIS A096969). In general, the numbers
of Hamiltonian paths on the 
grid graph for fixed 
are given by a linear recurrence.
The numbers of directed Hamiltonian cycles on the 
grid graph for 
, 2, ... are 0, 2, 0, 12, 0, 2144, 0, 9277152, ... (OEIS
A143246). In general, the numbers of Hamiltonian
cycles on the 
grid graph for fixed 
are given by a linear recurrence.
The numbers of (undirected) graph cycles on the 
grid graph for 
, 2, ... are 0, 1, 13, 213, 9349, 1222363, ... (OEIS A140517).
In general the number 
of 
-cycles on the 
grid graph is given by 
for 
odd and by a quadratic polynomial in 
for 
even, with the first few being
(E. Weisstein, Nov. 16, 2014).
The domination number of 
is given by
 |
(8)
|
for 
, as conjectured by Chang
(1992), confirmed up to an additive constant by Guichard (2004), and proved by Gonçalves
et al. (2011). Gonçalves et al. (2011) give a piecewise formula
for 
, but the expression given for
is not correct in all cases. A correct
formula for 
attributed to Hare appears as formula (6) in Chang and Clark (1993), which however
then proceeds to give an incorrect reformulation as formula (14).
A generalized grid graph, also known as an 
-dimensional lattice graph (e.g., Acharya and Gill 1981) can
also be defined as 
(e.g., Harary 1967, p. 28; Acharya and Gill 1981). Such graphs are somtimes
denoted 
or 
(e.g., Acharya and Gill
1981). A generalized grid graph has chromatic number
2, except the degenerate case of the singleton graph,
which has chromatic number 1. Special cases are
illustrated above and summarized in the table below.
is graceful
(Liu et al. 2012, Gallian 2018).