Simple cubic graphs with no short traveling salesman tour

2017/12/29 by Robert Lukoťka, Lukoťka, Robert, Ján Mazák +1
Computer Science · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM

paper · pdf · doi:10.48550/arxiv.1712.10167

arxiv created 2017/12/29 · arxiv updated 2018/01/01

Abstract

Let tsp(G) denote the length of a shortest travelling salesman tour in a graph G. We prove that for any ε>0, there exists a simple 2-connected planar cubic graph G₁ such that tsp(G₁)≥ (1.25-ε)⋅|V(G₁)|, a simple 2-connected bipartite cubic graph G₂ such that tsp(G₂)≥ (1.2-ε)⋅|V(G₂)|, and a simple 3-connected cubic graph G₃ such that tsp(G₃)≥ (1.125-ε)⋅|V(G₃)|.

Related

• Cubic TSP - a 1.3-approximation
• Improved Approximations for Cubic and Cubic Bipartite TSP
• TSP Tours in Cubic Graphs: Beyond 4/3
• A New Upper Bound for the Traveling Salesman Problem in Cubic Graphs
• The traveling salesman problem on cubic and subcubic graphs