Title: Tutte Paths and Even Covers
Michael Wigal, ACO PhD candidate, School of Mathematics
Date: July 11th
Time: 1:00 p.m.
Location: Skiles 005 and Zoom (TBD)
Advisor: Dr. Xingxing Yu, School of Mathematics, Georgia Institute of Technology
Committee:
Dr. Anton Bernshteyn, School of Mathematics, Georgia Institute of
Technology
Dr. Greg Blekherman, School of Mathematics, Georgia Institute of
Technology
Dr. Tom Kelly, School of Mathematics, Georgia Institute of
Technology
Dr. Will Perkins, School of Computer Science, Georgia Institute of
Technology
Reader: Dr. Kenta Ozeki, Environment and Information Sciences, Yokohama National University
Thesis draft: https://mwigal3.math.gatech.edu/thesis.pdf
Abstract: A 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 a large portion of the vertices (a graph is subcubic if its max 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áľ, and Mohar. Such a result is best possible as there is 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.
