A Conjecture on the Number of Hamiltonian Cycles on Thin Grid Cylinder Graphs
Olga Bodroza-Pantic, Harris Kwong, Milan Pantic
Abstract
We study the enumeration of Hamiltonian cycles on the thin grid
cylinder graph $C_m \times P_{n+1}$. We distinguish two types of
Hamiltonian cycles, and denote their numbers $h_m^A(n)$ and
$h_m^B(n)$. For fixed $m$, both of them satisfy linear homogeneous
recurrence relations with constant coefficients, and we derive their
generating functions and other related results for $m\leq10$. The
computational data we gathered suggests that $h^A_m(n)\sim h^B_m(n)$
when $m$ is even.
Full Text: PDF PostScript