Read More
Date: 24-3-2022
1469
Date: 24-2-2022
1418
Date: 20-4-2022
1620
|
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).
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.
|
|
تفوقت في الاختبار على الجميع.. فاكهة "خارقة" في عالم التغذية
|
|
|
|
|
أمين عام أوبك: النفط الخام والغاز الطبيعي "هبة من الله"
|
|
|
|
|
قسم شؤون المعارف ينظم دورة عن آليات عمل الفهارس الفنية للموسوعات والكتب لملاكاته
|
|
|