The number of Hamiltonian paths in a rectangular grid

被引：12

作者：

Collins, KL ^{[1
]}

Krompart, LB ^{[1
]}

机构：

[1] WESLEYAN UNIV,DEPT MATH,MIDDLETOWN,CT 06459

来源：

DISCRETE MATHEMATICS | 1997年 / 169卷 / 1-3期

关键词：

D O I：

10.1016/0012-365X(95)00330-Y

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

It is easy to find out which rectangular m vertex by n vertex grids have a Hamiltonian path from one corner to another using a checkerboard argument. However, it is quite difficult in general to count the total number of such paths. In this paper we give generating function answers for grids with fixed m for m = 1, 2, 3, 4, 5.

引用

页码：29 / 38

页数：10

共 50 条

[1] Reconfiguring Simple s, t Hamiltonian Paths in Rectangular Grid Graphs
Nishat, Rahnuma Islam
Srinivasan, Venkatesh
Whitesides, Sue
COMBINATORIAL ALGORITHMS, IWOCA 2021, 2021, 12757 : 501 - 515
[2] The Hamiltonian Path Graph is Connected for Simple s, t Paths in Rectangular Grid Graphs
Nishat, Rahnuma Islam
Srinivasan, Venkatesh
Whitesides, Sue
COMPUTING AND COMBINATORICS, COCOON 2022, 2022, 13595 : 463 - 475
[3] The hamiltonian path graph is connected for simple s, t paths in rectangular grid graphs
Nishat, Rahnuma Islam
Srinivasan, Venkatesh
Whitesides, Sue
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2024, 48 (04)
[4] AN EVALUATION OF THE NUMBER OF HAMILTONIAN PATHS
ORLAND, H
ITZYKSON, C
DEDOMINICIS, C
JOURNAL DE PHYSIQUE LETTRES, 1985, 46 (08): : L353 - L357
[5] On the maximum number of Hamiltonian paths in tournaments
Adler, I
Alon, N
Ross, SM
RANDOM STRUCTURES & ALGORITHMS, 2001, 18 (03) : 291 - 296
[6] THE MAXIMUM NUMBER OF HAMILTONIAN PATHS IN TOURNAMENTS
ALON, N
COMBINATORICA, 1990, 10 (04) : 319 - 324
[7] Hamiltonian Paths in Some Classes of Grid Graphs
Keshavarz-Kohjerdi, Fatemeh
Bagheri, Alireza
JOURNAL OF APPLIED MATHEMATICS, 2012,
[8] Reconfiguration of Hamiltonian Cycles in Rectangular Grid Graphs
Nishat, Rahnuma Islam
Whitesides, Sue
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2023, 34 (07) : 773 - 793
[9] A linear-time algorithm for finding Hamiltonian (s, t)-paths in odd-sized rectangular grid graphs with a rectangular hole
Fatemeh Keshavarz-Kohjerdi
Alireza Bagheri
The Journal of Supercomputing, 2017, 73 : 3821 - 3860
[10] A linear-time algorithm for finding Hamiltonian (s, t)-paths in odd-sized rectangular grid graphs with a rectangular hole
Keshavarz-Kohjerdi, Fatemeh
Bagheri, Alireza
JOURNAL OF SUPERCOMPUTING, 2017, 73 (09): : 3821 - 3860

← 1 2 3 4 5 →