Discrete Mathematics & Theoretical Computer Science, Vol 17, No 1 (2015)

Font Size:  Small  Medium  Large

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