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[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.

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["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).

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

			(1)
			(2)
			(3)
			(4)
			(5)
			(6)
			(7)

(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.