We prove that every simple 2-connected cubic n-vertex graph contains a
spanning closed walk of length at most 9n/7-1, and that such a walk can be
found in polynomial time. This yields a polynomial-time 9/7-approximation
algorithm for the graphic TSP for 2-connected cubic graphs, which improves the
previously known approximation factor of 1.3 for 2-connected cubic graphs. On
the negative side, we show that there exist simple 2-connected cubic n-vertex
graphs with no spanning closed walk of length less than 5n/4-1.

Read More
## Share Us With Colleagues