Grid Graph
A two-dimensional grid graph, also known as a square grid graph, is an 
lattice
graph 
that is the graph
Cartesian product 
of path
graphs on 
and 
vertices.
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 
.
The grid graph 
is implemented in the Wolfram
Language as GridGraph[m,
n, ...]. 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).
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)
|
 |  | ![{0 for n<4; 4[7(n-3)^2+7(n-3)-1] otherwise](/National_Library/20161222123739im_/https://mathworld.wolfram.com/images/equations/GridGraph/Inline46.gif) |
(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 can also be defined as 
.
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  |
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.
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.
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.
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.
Weisstein, Eric W. "Grid Graph." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/GridGraph.html
Contact the MathWorld Team
grid graph
