## Graph Theory and Combinatorics Seminar

- Event Type
- Seminar/Symposium
- Sponsor
- Department of Mathematics
- Location
- 111 Gregory Hall
- Date
- Sep 5, 2023 1:00 pm
- Speaker
- Michael Wigal (UIUC)
- Views
- 23
- Originating Calendar
- Combinatorics Research Area Calendar
Speaker: Michael Wigal (UIUC)

Title: Traveling Salesperson Walks in Subcubic Graphs

Abstract:

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.