Abstract
dc:description.abstractWhitney 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 × 3Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/1853/72035