A conjecture on the number of Hamiltonian cycles on thin grid cylinder graphs

Abstract

© 2015 Discrete Mathematics and Theoretical Computer Science (DMTCS). We study the enumeration of Hamiltonian cycles on the thin grid cylinder graph Cm x Pn+1. We distinguish two types of Hamiltonian cycles depending on their contractibility (as Jordan curves) and denote their numbers hmnc (n) and hmc (n). For fixed m, both of them satisfy linear homogeneous recurrence relations with constant coefficients. We derive their generating functions and other related results for m ≤ 10. The computational data we gathered suggests that hmnc (n) ∼ hmc (n) when m is even.