A 5/4 bound for graphic s-t path TSP on subcubic graphs

Abstract

We study the graphic s-t path TSP on subcubic graphs (maximum degree 3): given two vertices s, t, find a shortest walk from s to t that visits every vertex. Our main result is that the optimal 5/4 coefficient is attained for every terminal pair — including the difficult case where deleting both s and t disconnects the graph. Concretely, every pair of distinct vertices s, t in a simple 2-connected subcubic graph G admits a spanning s-t walk of length at most ⌊(5n+n_2(G))/4⌋−1, where n = |V(G)| and n_2(G) is the number of degree-2 vertices; the constant 5/4 cannot be improved, and a simple O(n^2) algorithm finds a walk of length at most ⌊(5n+n_2(G))/4⌋. An edge-rooted even-cover theorem of Wigal, Yoo, and Yu, combined with a short conversion lemma proved here, gives a bound of this form only when s and t are the two endpoints of a given edge; we remove that adjacency restriction. For cubic graphs (n_2(G) = 0) the bound reads ⌊5n/4⌋−1, to our knowledge the first 5/4 bound for cubic path TSP proved directly rather than through the general path-to-tour reduction.