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.

Source : oai:HAL:hal-01196857v1

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]

This page has been seen 115 times.

This article's PDF has been downloaded 223 times.