Grid Graph
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).
Unfortunately, the convention on 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[![<span style=]()
{" src="https://mathworld.wolfram.com/images/equations/GridGraph/Inline7.svg" style="height:22px; width:6px" />m, n, ...![<span style=]()
}" src="https://mathworld.wolfram.com/images/equations/GridGraph/Inline8.svg" style="height:22px; width:6px" />] 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.
The particular case of an 
rectangular grid graph is sometimes known as a square grid graph.
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[![<span style=]()
{" src="https://mathworld.wolfram.com/images/equations/GridGraph/Inline34.svg" style="height:22px; width:6px" />"Grid", ![<span style=]()
{" src="https://mathworld.wolfram.com/images/equations/GridGraph/Inline35.svg" style="height:22px; width:6px" />m, ..., r, ...![<span style=]()
}" src="https://mathworld.wolfram.com/images/equations/GridGraph/Inline36.svg" style="height:22px; width:6px" />![<span style=]()
}" src="https://mathworld.wolfram.com/images/equations/GridGraph/Inline37.svg" style="height:22px; width:6px" />].
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).
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.
| grid graph |
special case |
 |
path graph  |
 |
ladder graph  |
 |
square graph  |
 |
domino graph |
 |
cubical graph  |
 |
hypercube graph  |
is graceful (Liu et al. 2012, Gallian 2018).
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. Dec. 21, 2018.
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.
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.
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.
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.
