Path TSP Walks on Cubic Graphs

For every simple 2-vertex-connected cubic graph G on n ≥ 4 vertices and every distinct pair of terminals s, t ∈ V (G), there is a spanning s-t walk of length at most ⌊5n/4⌋, constructible in O (n²) time. If st ∈ E (G), or if st ∉ E (G) and G − s, t is connected, the bound improves to ⌊5n/4⌋ − 1; the improvement is constructive in the adjacent case and existential otherwise. The proof converts the edge-rooted even-cover theorem of Wigal, Yoo, and Yu into a fixed-endpoint statement. The adjacent-terminal case opens an even cover at the terminal edge; for non-adjacent terminals, a constant-size split-and-subdivide gadget creates a marked edge whose contraction back to G forces a four-loop deletion, preserving the 5/4 coefficient. On simple cubic 3-edge-connected graphs the nonseparation condition is automatic, and combining the walk-length bound with LP (G, s, t) ≥ n − 1 gives an asymptotic 5/4 upper bound on the path Held–Karp gap. A complementary 9/8 asymptotic lower bound follows from an exact adjacent-terminal LP certificate (LP = n − 1) and the Lukoťka–Mazák cubic tour examples, so the asymptotic gap on this class lies in 9/8, 5/4. The 5/4 coefficient is tight on the broader simple 2-vertex-connected cubic class via the Dvořák–Král'–Mohar tour examples.