Simple cubic graphs with no short traveling salesman tour

Robert Lukoťka; Ján Mazák

paper

Simple cubic graphs with no short traveling salesman tour

arXiv:1712.10167

Abstract

Let $t s p (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_{1}$ such that $t s p (G_{1}) \geq (1.25 - ε) \cdot ∣ V (G_{1}) ∣$ , a simple $2$ -connected bipartite cubic graph $G_{2}$ such that $t s p (G_{2}) \geq (1.2 - ε) \cdot ∣ V (G_{2}) ∣$ , and a simple $3$ -connected cubic graph $G_{3}$ such that $t s p (G_{3}) \geq (1.125 - ε) \cdot ∣ V (G_{3}) ∣$ .