Back to search

Georgia Institute of Technology

Counting Hamiltonian cycles in planar triangulations

Abstract

dc:description.abstract

Whitney showed that every planar triangulation without separating $3$-cycles is Hamiltonian. This result was extended to all $4$-connected planar graphs by Tutte. Hakimi, Schmeichel, and Thomassen showed the first lower bound n/\log 2 n for the number of Hamiltonian cycles in every $n$-vertex $4$-connected planar triangulation and, in the same paper, they conjectured that this number is at least $2(n-2)(n-4)$, with equality if and only if $G$ is a double wheel. We show that every $4$-connected planar triangulation on $n$ vertices has \Omega(n2) Hamiltonian cycles. Moreover, we show that if $G$ is a $4$-connected planar triangulation on $n$ vertices and the distance between any two vertices of degree $4$ in $G$ is at least $3$, then $G$ has 2\Omega(n1/4) Hamiltonian cycles.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Mathematics
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2023

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Liu, Xiaonan
Advisor dc:contributor.advisor
  • Yu, Xingxing
Committee members dc:contributor.committeemember
  • Bernshteyn, Anton
  • Blekherman, Greg
  • Kelly, Tom
  • Perkins, Will

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
https://hdl.handle.net/1853/72035

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Liu, Xiaonan. Counting Hamiltonian cycles in planar triangulations. Doctoral thesis, Georgia Institute of Technology, 2023. https://hdl.handle.net/1853/72035