Grid Graph

👁 DOWNLOAD Mathematica Notebook
Download Wolfram Notebook

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 👁 m×n
lattice graph that is the graph Cartesian product 👁 P_m square P_n
of path graphs on 👁 m
and 👁 n
vertices. The 👁 m×n
grid graph is sometimes denoted 👁 L(m,n)
(e.g., Acharya and Gill 1981). The particular case of an 👁 n×n
rectangular grid graph is sometimes known as a square grid graph. By analogy with the KC graph and KP graph, the 👁 m×n
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 [👁 {
m, n, ...👁 }
] also adopts this ordering, returning an embedding in which 👁 m
corresponds to the height and 👁 n
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 👁 7×4
grid graph or the 👁 4×7
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 👁 (i,j)
with 👁 i=0
, 1, ..., 👁 m
and 👁 j=0
, 1, ..., 👁 n
. If Harary's ordered pairs are interpreted as Cartesian coordinates, a grid graph with parameters 👁 m
and 👁 n
consists of 👁 m+1
vertices along the 👁 x
-axis and 👁 n+1
along the 👁 y
-axis. This is consistent with the interpretaion of 👁 P_m square P_n
in the graph Cartesian product as paths with 👁 m
and 👁 n
edges (and hence 👁 m+1
and 👁 n+1
vertices), respectively. The convention that 👁 G(alpha_1,alpha_2,...
) is a grid graph made of the graph Cartesian product of paths of length 👁 alpha_1
, 👁 alpha_2
, ... is also used by Millichap and Salinas (2022).

Note that Brouwer et al. (1989, p. 440) use the term "👁 m×n
grid" to refer to the line graph 👁 L(K_(m,n))
of the complete bipartite graph 👁 K_(m,n)
, known in this work as the rook graph 👁 K_m square K_n
.

Precomputed properties for a number of grid graphs are available using [👁 {
, 👁 {
m, ..., r, ...👁 }
👁 }
].

A grid graph 👁 P_m square P_n
has 👁 mn
vertices and 👁 (m-1)n+(n-1)m=2mn-m-n
edges.

A grid graph 👁 P_m square P_n
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). 👁 m×n
and 👁 n×n
grid graphs are graceful (Acharya and Gill 1981, Gallian 2018).

👁 d
-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 👁 n×n
grid graph for 👁 n=1
, 2, ... are given by 1, 8, 40, 552, 8648, 458696, 27070560, ... (OEIS A096969). In general, the numbers of Hamiltonian paths on the 👁 m×n
grid graph for fixed 👁 m
are given by a linear recurrence.

The numbers of directed Hamiltonian cycles on the 👁 n×n
grid graph for 👁 n=1
, 2, ... are 0, 2, 0, 12, 0, 2144, 0, 9277152, ... (OEIS A143246). In general, the numbers of Hamiltonian cycles on the 👁 m×n
grid graph for fixed 👁 m
are given by a linear recurrence.

The numbers of (undirected) graph cycles on the 👁 n×n
grid graph for 👁 n=1
, 2, ... are 0, 1, 13, 213, 9349, 1222363, ... (OEIS A140517). In general the number 👁 c_k
of 👁 k
-cycles on the 👁 n×n
grid graph is given by 👁 c_k=0
for 👁 k
odd and by a quadratic polynomial in 👁 n
for 👁 k
even, with the first few being

(E. Weisstein, Nov. 16, 2014).

The domination number of 👁 P_m square P_n
is given by

for 👁 16<=m<=n
, 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 👁 m<16
, but the expression given for 👁 n=16
is not correct in all cases. A correct formula for 👁 n=16
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 👁 n×n
grid graphs up to 👁 n=22
.

A generalized grid graph, also known as an 👁 n
-dimensional lattice graph (e.g., Acharya and Gill 1981) can also be defined as 👁 P_m square P_n square P_r square ...
(e.g., Harary 1967, p. 28; Acharya and Gill 1981). Such graphs are somtimes denoted 👁 G_(m,n,r,...)
or 👁 L(m,n,r,...)
(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.

👁 P_m square P_n square P_2
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 👁 G square P_n
." Ars Combin. 49, 129-154, 1998.Chang, T. Y. and Clark, W. E. "The Domination Numbers of the 👁 5×n
and 👁 6×n
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.Millichap, C. and Salinas, F. "Embedding Grid Graphs on Surfaces." 18 Apr 2022. https://arxiv.org/abs/2104.12270.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 👁 n
-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

Grid Graph

Cite this as:

Weisstein, Eric W. "Grid Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/GridGraph.html

Subject classifications