Abstract | ||
---|---|---|
Hakimi, Schmeichel and Thomassen showed in 1979 that every 4-connected triangu-lation on n vertices has at least n/log(2) n hamiltonian cycles, and conjectured that the sharp lower bound is 2(n - 2)(n - 4). Recently, Brinkmann, Souffriau and Van Cleemput gave an improved lower bound 12/5 (n - 2). In this paper we show that every 4-connected triangulation with O(log n) 4-separators has Omega(n(2)/log(2) n) hamiltonian cycles. (c) 2020 Elsevier B.V. All rights reserved. |
Year | DOI | Venue |
---|---|---|
2020 | 10.1016/j.disc.2020.112126 | DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
4-connected plane triangulations, Hamiltonian cycles, Counting base | Journal | 343 |
Issue | ISSN | Citations |
12 | 0012-365X | 0 |
PageRank | References | Authors |
0.34 | 0 | 1 |
Name | Order | Citations | PageRank |
---|---|---|---|
On-Hei Solomon Lo | 1 | 0 | 2.03 |