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.
Type de document :
Article dans une revue
Discrete Mathematics and Theoretical Computer Science, DMTCS, 2015, Vol. 17 no. 1 (in progress) (1), pp.219--240
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01196857
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 10 septembre 2015 - 15:17:19
Dernière modification le : jeudi 7 septembre 2017 - 01:03:44
Document(s) archivé(s) le : mardi 29 décembre 2015 - 00:01:57

Fichier

dmtcs-17-1-15.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01196857, version 1

Collections

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〉

Partager

Métriques

Consultations de la notice

83

Téléchargements de fichiers

156