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

Cite this

Alahmadi, A. ; Aldred, R.E.L. ; Thomassen, Carsten. / Cycles in 5-connected triangulations. In: Journal of Combinatorial Theory. Series B. 2020 ; Vol. 140. pp. 27-44.
@article{a2393ae6897542549a250194117fb837,
title = "Cycles in 5-connected triangulations",
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.",
keywords = "Cycles, Triangulation of a surface, Planar triangulation, Projective planar triangulation",
author = "A. Alahmadi and R.E.L. Aldred and Carsten Thomassen",
year = "2020",
doi = "10.1016/j.jctb.2019.04.005",
language = "English",
volume = "140",
pages = "27--44",
journal = "Journal of Combinatorial Theory. Series B",
issn = "0095-8956",
publisher = "Academic Press",

}

Cycles in 5-connected triangulations. / Alahmadi, A.; Aldred, R.E.L.; Thomassen, Carsten.

In: Journal of Combinatorial Theory. Series B, Vol. 140, 2020, p. 27-44.

Research output: Contribution to journalJournal articleResearchpeer-review

TY - JOUR

T1 - Cycles in 5-connected triangulations

AU - Alahmadi, A.

AU - Aldred, R.E.L.

AU - Thomassen, Carsten

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

KW - Cycles

KW - Triangulation of a surface

KW - Planar triangulation

KW - Projective planar triangulation

U2 - 10.1016/j.jctb.2019.04.005

DO - 10.1016/j.jctb.2019.04.005

M3 - Journal article

VL - 140

SP - 27

EP - 44

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

SN - 0095-8956

ER -