A conjecture on the number of Hamiltonian cycles on thin grid cylinder graphs. (English) Zbl 1311.05102

Bodroža-Pantić, Olga; Kwong, Harris; Pantić, Milan

Discrete Math. Theor. Comput. Sci. 17, No. 1, 219-240 (2015).

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.

MSC:

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

Keywords:

Hamiltonian cycles; generating functions; thin grid cylinder; contractible curves