Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6871168 | Discrete Applied Mathematics | 2018 | 5 Pages |
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
Robert LukoÅ¥ka, Ján Mazák,