zbMATH — the first resource for mathematics

A conjecture on the number of Hamiltonian cycles on thin grid cylinder graphs. (English) Zbl 1311.05102
Summary: 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.

05C45 Eulerian and Hamiltonian graphs
05C30 Enumeration in graph theory
05A15 Exact enumeration problems, generating functions
Full Text: Link