Advanced search
1 file | 313.29 KB

On the number of hamiltonian cycles in triangulations with few separating triangles

(2018) JOURNAL OF GRAPH THEORY. 87(2). p.164-175
Author
Organization
Abstract
In this article, we investigate the number of hamiltonian cycles in triangulations. We improve a lower bound of vertical bar V vertical bar/log2 vertical bar V vertical bar for the number of hamiltonian cycles in triangulations without separating triangles (4-connected triangulations) by Hakimi, Schmeichel, and Thomassen to a linear lower bound and show that a linear lower bound even holds in the case of triangulations with one separating triangle. We confirm their conjecture about the number of hamiltonian cycles in triangulations without separating triangles for up to 25 vertices and give computational results and constructions for triangulations with a small number of hamiltonian cycles and 1-5 separating triangles.
Keywords
hamiltonian cycle, maximal planar graph, triangulation

Downloads

  • (...).pdf
    • full text
    • |
    • UGent only
    • |
    • PDF
    • |
    • 313.29 KB

Citation

Please use this url to cite or link to this publication:

Chicago
Brinkmann, Gunnar, Jasper Souffriau, and Nicolas Van Cleemput. 2018. “On the Number of Hamiltonian Cycles in Triangulations with Few Separating Triangles.” Journal of Graph Theory 87 (2): 164–175.
APA
Brinkmann, Gunnar, Souffriau, J., & Van Cleemput, N. (2018). On the number of hamiltonian cycles in triangulations with few separating triangles. JOURNAL OF GRAPH THEORY, 87(2), 164–175.
Vancouver
1.
Brinkmann G, Souffriau J, Van Cleemput N. On the number of hamiltonian cycles in triangulations with few separating triangles. JOURNAL OF GRAPH THEORY. 2018;87(2):164–75.
MLA
Brinkmann, Gunnar, Jasper Souffriau, and Nicolas Van Cleemput. “On the Number of Hamiltonian Cycles in Triangulations with Few Separating Triangles.” JOURNAL OF GRAPH THEORY 87.2 (2018): 164–175. Print.
@article{8522233,
  abstract     = {In this article, we investigate the number of hamiltonian cycles in triangulations. We improve a lower bound of vertical bar V vertical bar/log2 vertical bar V vertical bar for the number of hamiltonian cycles in triangulations without separating triangles (4-connected triangulations) by Hakimi, Schmeichel, and Thomassen to a linear lower bound and show that a linear lower bound even holds in the case of triangulations with one separating triangle. We confirm their conjecture about the number of hamiltonian cycles in triangulations without separating triangles for up to 25 vertices and give computational results and constructions for triangulations with a small number of hamiltonian cycles and 1-5 separating triangles.},
  author       = {Brinkmann, Gunnar and Souffriau, Jasper and Van Cleemput, Nicolas},
  issn         = {0364-9024},
  journal      = {JOURNAL OF GRAPH THEORY},
  language     = {eng},
  number       = {2},
  pages        = {164--175},
  title        = {On the number of hamiltonian cycles in triangulations with few separating triangles},
  url          = {http://dx.doi.org/10.1002/jgt.22149},
  volume       = {87},
  year         = {2018},
}

Altmetric
View in Altmetric
Web of Science
Times cited: