Cycles in 5-connected triangulations

A. Alahmadi, R.E.L. Aldred, Carsten Thomassen*

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

Abstract

We show that in 5-connected planar and projective planar triangulations on n vertices, the number of Hamiltonian cycles grows exponentially with n. The result is best possible in the sense that 4-connected triangulations on n vertices on any fixed surface may have only polynomially many cycles. Also, there is an infinite class of 5-connected graphs (not on a fixed surface) which have only polynomially many cycles. The result also extends to 5-connected triangulations of the torus if a long standing conjecture of Nash-Williams holds. For any fixed surface, we show that every 5-connected triangulation of large face-width on that surface contains exponentially many cycles.
Original languageEnglish
JournalJournal of Combinatorial Theory. Series B
Volume140
Pages (from-to)27-44
Number of pages18
ISSN0095-8956
DOIs
Publication statusPublished - 2020

Keywords

  • Cycles
  • Triangulation of a surface
  • Planar triangulation
  • Projective planar triangulation

Fingerprint Dive into the research topics of 'Cycles in 5-connected triangulations'. Together they form a unique fingerprint.

Cite this