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. By analogy with the KC graph
and KP graph, the 
grid graph could also be called a "PP 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).
Mertens (2024) computed the domination polynomial and numbers of dominating sets for 
grid graphs up to 
.
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).
See also
Cycle Graph, Domino Graph, Hypercube, Ladder Graph, Lattice Graph, Path Graph, Rook Graph, Square Grid, Torus Grid Graph
Explore with Wolfram|Alpha
References
Acharya, B. D. and Gill, M. K. "On the Index of Gracefulness of a Graph and the Gracefulness of Two-Dimensional Square Lattice
Graphs." Indian J. Math. 23, 81-94. 1981.Brouwer,
A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular
Graphs. New York: Springer-Verlag, 1989.Chang, T. Y. Domination
Numbers of Grid Graphs. Ph.D. thesis. Tampa, FL: University of South Florida,
1992.Faase, F. "On the Number of Specific Spanning Subgraphs of
the Graphs 
."
Ars Combin. 49, 129-154, 1998.Chang, T. Y. and Clark,
W. E. "The Domination Numbers of the 
and 
Grid Graphs." J. Graph Th. 17, 81-107,
1993.Gallian, J. "Dynamic Survey of Graph Labeling." Elec.
J. Combin. DS6. Oct. 30, 2025. https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.Gonçalves,
D.; Pinlou, A.; Rao, M.; and Thomassé, S. "The Domination Number of Grids."
SIAM J. Discrete Math. 25, 1443-1453, 2011.Guichard, D. R.
"A Lower Bound for the Domination Number of Complete Grid Graphs." J.
Combin. Math. Combin. Comput. 49, 215-220, 2004.Harary, F.
Graph
Theory. Reading, MA: Addison-Wesley, p. 194, 1994.Harary,
F. "Graphical Enumeration Problems." In Graph
Theory and Theoretical Physics (Ed. F. Harary). London: Academic Press,
pp. 1-41, 1967.Hedetniemi, S. M.; Hedetniemi, S. T.;
and Slater, P. S. "Which Grids Are Hamiltonian?" Congr. Numer. 29,
511-524, 1980.Itai, A.; Papadimitriou, C. H.; and Szwarcfiter,
J. L. "Hamilton Paths in Grid Graphs." SIAM J. Comput. 11,
676-686, 1982.Iwashita, H.; Nakazawa, Y.; Kawahara, J.; Uno, T.; and
Minato, S.-I. "Efficient Computation of the Number of Paths in a Grid Graph
with Minimal Perfect Hash Functions." TCS Technical Report. No. TCS-TR-A-13-64.
Hokkaido University Division of Computer Science. Apr. 26, 2013.Jacobsen,
J. L. "Exact Enumeration of Hamiltonian Circuits, Walks and Chains in Two
and Three Dimensions." J. Phys. A: Math. Theor. 40, 14667-14678,
2007.Karavaev, A. M. "FlowProblem: Hamiltonian Cycles."
http://flowproblem.ru/paths/hamilton-cycles.Karavaev,
A. M. "FlowProblem: Hamiltonian Paths." http://flowproblem.ru/paths/hamilton-paths.Liu,
J. B.; Zou, T.; and Lu, Y. "Gracefulness of Cartesian Product Graphs."
Pure Appl. Math. (Xi'an) 28, 329-332 and 362, 2012.Mertens,
S. "Domination Polynomials of the Grid, the Cylinder, the Torus, and the King
Graph." 15 Aug 2024. https://arxiv.org/abs/2408.08053.Pönitz,
A. "Computing Invariants in Graphs of Small Bandwidth." Math. in Computers
and Sim. 49, 179-191, 1999.Reddy, V. and Skiena, S. "Frequencies
of Large Distances in Integer Lattices." Technical Report, Department of Computer
Science. Stony Brook, NY: State University of New York, Stony Brook, 1989.Schmalz,
T. G.; Hite, G. E.; and Klein, D. J. "Compact Self-Avoiding Circuits
on Two-Dimensional Lattices." J. Phys. A: Math. Gen. 17, 445-453,
1984.Simmons, G. J. "Almost All 
-Dimensional Rectangular Lattices Are Hamilton-Laceable."
In Proceedings
of the Ninth Southeastern Conference on Combinatorics, Graph Theory, and Computing
(Florida Atlantic Univ., Boca Raton, Fla., 1978) (Ed. F. Hoffman, D. McCarthy,
R. C. Mullin, and R. G. Stanton). Winnipeg, Manitoba: Utilitas
Mathematica Publishing, pp. 649-661, 1978.Skiena, S. "Grid
Graphs." §4.2.4 in Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading,
MA: Addison-Wesley, pp. 147-148, 1990.Sloane, N. J. A.
Sequences A096969, A140517,
and A143246 in "The On-Line Encyclopedia
of Integer Sequences."Umans, C. M. "An Algorithm for
Finding Hamiltonian Cycles in Grid graphs without Holes." Undergraduate thesis.Umans,
C. and Lenhart, W. "Hamiltonian Cycles in Solid Grid Graphs." In Proc.
38th Annual IEEE Sympos. Found. Comput. Sci. pp. 496-505, 1997.Zamfirescu,
C. and Zamfirescu, T. "Hamiltonian Properties of Grid Graphs." SIAM
J. Disc. Math. 5, 564-570, 1992.
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Grid Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GridGraph.html