Open AccessEnumeration of Hamiltonian cycles on a thick grid cylinder - part I: Non-contractible Hamiltonian cycles
Author(s) -
Olga Bodroža-Pantić,
Harris Kwong,
Jelena Djokić,
Rade Doroslovački,
M. Pantić
Publication year - 2019
Publication title -
applicable analysis and discrete mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.69
H-Index - 26
eISSN - 2406-100X
pISSN - 1452-8630
DOI - 10.2298/aadm171215025b
Subject(s) - contractible space , mathematics , enumeration , conjecture , hamiltonian (control theory) , combinatorics , hamiltonian path , grid , graph , cylinder , discrete mathematics , geometry , mathematical optimization
In a recent paper, we have studied the enumeration of Hamiltonian cycles (abbreviated HCs) on the grid cylinder graph Pm+1 x Cn, where m grows while n is fixed. In this sequel, we study a much harder problem of enumerating HCs on the same graph only this time letting n grow while m is fixed. We propose a characterization for non-contractible HCs which enables us to prove that their numbers hnc, m (n) satisfy a recurrence relation for every fixed m. From the computational data, we conjecture that the coefficient for the dominant positive characteristic root in the explicit formula for hnc,m (n) is 1.