{"id":"arxiv/2608.11038","url":"https://arxiv.org/abs/2608.11038","tags":["cs.DS","cs.DM","math.CO"],"score":0,"title":"A 5/4 bound for graphic $s$-$t$ path TSP on subcubic graphs","domain":"cs.DS","source":"arxiv","authors":["Junho Hwang"],"reviews":0,"subject":"cs.DS","summary":"We study the graphic $s$-$t$ path TSP on subcubic graphs (maximum degree 3): given distinct vertices $s,t$, find a shortest $s$-$t$ walk that visits every vertex. We prove an upper bound with the asymptotically optimal leading coefficient $5/4$ for every terminal pair, even when $G-\\{s,t\\}$ is disconnected. Specifically, every simple 2-connected subcubic graph $G$ on $n$ vertices has a spanning $s$-$t$ walk of length at most $\\lfloor(5n+n_2(G))/4\\rfloor$, where $n_2(G)$ counts its degree-2 vertices. An $O(n^2)$-time algorithm attains this bound. Combining an edge-rooted even-cover theorem of…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-11","reactions":{}}