Urbana Campus Research Calendar (OVCRI)

View Full Calendar

Graph Theory and Combinatorics Seminar

Event Type
Department of Mathematics
111 Gregory Hall
Sep 5, 2023   1:00 pm  
Michael Wigal (UIUC)
Originating Calendar
Combinatorics Research Area Calendar

Speaker: Michael Wigal (UIUC)

Title: Traveling Salesperson Walks in Subcubic Graphs


We will show that if G is a 2-connected subcubic graph on n vertices with 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. This upper bound is best possible. In particular, there are infinitely many subcubic (respectively, cubic) graphs whose minimum TSP walks have length (5n + n_2)/4  - 1 (respectively, 5n/4 - 2). We will outline how a quadratic-time algorithm can be obtained from the proof, thus yielding a 5/4-approximation algorithm for graphic TSP of simple cubic graphs, improving upon the prior best guarantee of 9/7.

Joint work with Youngho Yoo and Xingxing Yu.


link for robots only