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

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.
Keywords :
Document type :
Journal articles
Domain :

Cited literature [19 references]

https://hal.inria.fr/hal-01196857
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, September 10, 2015 - 3:17:19 PM
Last modification on : Tuesday, August 13, 2019 - 11:56:01 AM
Long-term archiving on: : Tuesday, December 29, 2015 - 12:01:57 AM

File

dmtcs-17-1-15.pdf
Publisher files allowed on an open archive

Identifiers

• HAL Id : hal-01196857, version 1

Citation

Olga Bodroža-Pantić, Harris Kwong, Milan Pantić. A conjecture on the number of Hamiltonian cycles on thin grid cylinder graphs. Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no. 1 (in progress) (1), pp.219--240. ⟨hal-01196857⟩

Record views