**Tuesday, Dec 7,** **3pm ET** (8pm GMT, 9am Wed NZDT)

**Michael Wigal**, Georgia Tech

**Approximating TSP walks in subcubic graphs**

#####

**Abstract:**

##### We will show that if $G$ is a $2$-connected simple subcubic graph on $n$ vertices with $n_2$ vertices of degree $2$, then $G$ has a TSP walk of length at most $5n/4 + 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/4 + n_2/4 -1$ (respectively, $5n/4 – 2$). Our proof implies a quadratic-time algorithm for finding such a TSP walk, thereby giving a $5/4$ approximation algorithm for the graphic TSP on simple cubic graphs and improving on the previously best known approximation ratio of $9/7$.

Joint work with Youngho Yoo and Xingxing Yu.