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 Cm×Pn+1. We distinguish two types of Hamiltonian cycles, and denote their numbers hAm(n) and hBm(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 m10. The computational data we gathered suggests that hAm(n)hBm(n) when m is even.


Volume: Vol. 17 no. 1
Section: Graph Theory
Published on: March 28, 2015
Submitted on: March 16, 2014
Keywords: Hamiltonian cycles,generating functions,thin grid cylinder,contractible curves,[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
  • 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
  • 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
  • New products based on cereals and pseudocereals from organic production; Funder: Ministry of Education, Science and Technological Development of Republic of Serbia; Code: 46005

1 Document citing this article

Consultation statistics

This page has been seen 557 times.
This article's PDF has been downloaded 618 times.