Abstract
dc:description.abstractA Tutte path of a graph G is a path P of G such that every component of G - P has at most three attachments on P. Tutte paths are well studied in the literature due to their applications towards the Hamiltonian cycle problem. We prove the existence of Tutte paths in which the number of components is bounded for circuit graphs, a natural family of planar graphs which generalizes 3-connected planar graphs. As a consequence, we obtain a sharp lower bound for the circumference of essentially 4-connected planar graphs, answering a conjecture of Fabrici, Harant, Mohr, and Schmidt. The Traveling Salesperson Problem (TSP) is a foundational problem in the optimization literature and generalizes the Hamiltonian cycle problem. Motivated by the TSP, we investigate even covers of subcubic graphs, i.e., finding a small number of cycles that cover the majority of the vertices (a graph is subcubic if its maximum degree is 3). As an application, we will show that if G is a 2-connected subcubic graph with n vertices and n_2 vertices of degree 2, then G has a TSP walk of length at most (5n+n_2)/4−1, establishing a conjecture of Dvořák, Král', and Mohar. There are an infinite family of subcubic (respectively, cubic) graphs whose minimum TSP walk have length (5n + n_2)/4 − 1 (respectively, 5n/4 − 2). As this walk can be found in quadratic time, this provides a state-of-the-art 5/4-approximation algorithm for the TSP on 2-connected cubic graphs, improving the prior best guarantee of 9/7.
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
-
- Wigal, Michael Carroll
- Advisor dc:contributor.advisor
-
- Yu, Xingxing
- Committee members dc:contributor.committeemember
-
- Bernshteyn, Anton
- Blekherman, Greg
- Kelly, Tom
- Perkins, Will
Subjects
dc:subject × 5Rights
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/1853/72731