pith. sign in

arxiv: 1712.10167 · v1 · pith:RCKCYW62new · submitted 2017-12-29 · 💻 cs.DM

Simple cubic graphs with no short traveling salesman tour

classification 💻 cs.DM
keywords cubicgraphsimplevarepsiloncdotconnectedsalesmantour
0
0 comments X
read the original abstract

Let $tsp(G)$ denote the length of a shortest travelling salesman tour in a graph $G$. We prove that for any $\varepsilon>0$, there exists a simple $2$-connected planar cubic graph $G_1$ such that $tsp(G_1)\ge (1.25-\varepsilon)\cdot|V(G_1)|$, a simple $2$-connected bipartite cubic graph $G_2$ such that $tsp(G_2)\ge (1.2-\varepsilon)\cdot|V(G_2)|$, and a simple $3$-connected cubic graph $G_3$ such that $tsp(G_3)\ge (1.125-\varepsilon)\cdot|V(G_3)|$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.