Olga Bodroža-Pantić ; Harris Kwong ; Milan Pantić - A conjecture on the number of Hamiltonian cycles on thin grid cylinder graphs

dmtcs:2113 - Discrete Mathematics & Theoretical Computer Science, March 28, 2015, Vol. 17 no. 1 - https://doi.org/10.46298/dmtcs.2113
A conjecture on the number of Hamiltonian cycles on thin grid cylinder graphsArticle

Authors: Olga Bodroža-Pantić ORCID1; Harris Kwong 2; Milan Pantić 3

  • 1 Department of Mathematics and Informatics [Novi Sad]
  • 2 Mathematical Sciences Department [Fredonia, NY]
  • 3 Department of Physics [Novi Sad]

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.


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]
Funding:
    Source : OpenAIRE Graph
  • New products based on cereals and pseudocereals from organic production; Funder: Ministry of Education, Science and Technological Development of Republic of Serbia; Code: 46005
  • Algebraic, logical and combinatorial methods with applications in theoretical computer science; Funder: Ministry of Education, Science and Technological Development of Republic of Serbia; Code: 174018
  • The influence of elementary excitations and conformations to physical properties of the new materials based on strongly correlated low-dimensional systems; Funder: Ministry of Education, Science and Technological Development of Republic of Serbia; Code: 171009

1 Document citing this article

Consultation statistics

This page has been seen 358 times.
This article's PDF has been downloaded 474 times.