The number of Hamiltonian paths in a rectangular grid (Q1357721): Difference between revisions
From MaRDI portal
Set profile property. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / DOI | |||
Property / DOI: 10.1016/0012-365x(95)00330-y / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3772257 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Hamilton Paths in Grid Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Enumeration of Hamiltonian cycles in a squared rectangle / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4014296 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4748889 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Enumeration of Tours in Hamiltonian Rectangular Lattice Graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3748279 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the number of Hamiltonian cycles of \(P_ 4\times{} P_ n\) / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Hamiltonian Properties of Grid Graphs / rank | |||
Normal rank |
Latest revision as of 16:41, 27 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The number of Hamiltonian paths in a rectangular grid |
scientific article |
Statements
The number of Hamiltonian paths in a rectangular grid (English)
0 references
12 January 1998
0 references
Given a rectangular \(m\) vertex by \(n\) vertex grid, let \(f(m,n)\) be the number of Hamiltonian paths from the lower left corner (LL) to the upper right corner (UR). The paper gives a generating function which is the quotient of two polynomials, and contains the sequence \(f(m,1)\), \(f(m,2)\), \(f(m,3)\), \(f(m,4),\dots\) as the coefficients in its Taylor series expansion about 0. It is shown that for \(m=3\) the grid has \(2^{n-2}\) Hamiltonian paths from its LL corner to its UR corner and from its LL corner to its LR corner.
0 references
grid
0 references
Hamiltonian paths
0 references
generating function
0 references