Back to search

Georgia Institute of Technology

Tutte paths and even covers

Abstract

dc:description.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 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 × 5

Rights

Language dc:language.iso
en_US

Identifiers

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

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

Wigal, Michael Carroll. Tutte paths and even covers. Doctoral thesis, Georgia Institute of Technology, 2023. https://hdl.handle.net/1853/72731