Simple cubic graphs with no short traveling salesman tour
classification
💻 cs.DM
keywords
cubicgraphsimplevarepsiloncdotconnectedsalesmantour
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.