## Bodroža-Pantić, Olga and Kwong, Harris and Pantić, Milan - A conjecture on the number of Hamiltonian cycles on thin grid cylinder graphs

dmtcs:2113 - Discrete Mathematics & Theoretical Computer Science, March 28, 2015, Vol. 17 no. 1
A conjecture on the number of Hamiltonian cycles on thin grid cylinder graphs

Authors: Bodroža-Pantić, Olga and Kwong, Harris and Pantić, Milan

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.

Volume: Vol. 17 no. 1
Section: Graph Theory
Published on: March 28, 2015
Submitted on: March 16, 2014
Keywords: contractible curves,thin grid cylinder,generating functions,Hamiltonian cycles,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-HC] Computer Science [cs]/Human-Computer Interaction [cs.HC]