Article ID Journal Published Year Pages File Type
6871168 Discrete Applied Mathematics 2018 5 Pages PDF
Abstract
Let tsp(G) denote the length of a shortest traveling salesman tour in a graph G. We prove that for any ε>0, there exists a simple 2-connected planar cubic graph G1 such that tsp(G1)≥(1.25−ε)⋅|V(G1)|, a simple 2-connected bipartite cubic graph G2 such that tsp(G2)≥(1.2−ε)⋅|V(G2)|, and a simple 3-connected cubic graph G3 such that tsp(G3)≥(1.125−ε)⋅|V(G3)|.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,