Premium
On the number of hamiltonian cycles in triangulations with few separating triangles
Author(s) -
Brinkmann Gunnar,
Souffriau Jasper,
Cleemput Nico
Publication year - 2018
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22149
Subject(s) - mathematics , combinatorics , conjecture , hamiltonian (control theory) , hamiltonian path , upper and lower bounds , mathematical analysis , graph , mathematical optimization
Abstract In this article, we investigate the number of hamiltonian cycles in triangulations. We improve a lower bound of| V | / log 2 | V |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.