3 problems

0 votes0 replies0 views
Buratti's Hamiltonian path edge-length conjecture
Let $K_n$ be the complete graph on $n$ vertices, and let edge lengths be the integers from $1$ through $\lfloor n/2\rfloor$ , with the length of an edge defined by the cyclic distan…
Conjectureopencirculant-graphs hamiltonian-paths tsparXiv posted 2 days ago
0 votes0 replies0 views
The four-thirds integrality-gap conjecture for the metric TSP subtour LP
Four-thirds integrality-gap conjecture. The subtour elimination linear program for the metric TSP has integrality gap exactly $\frac{4}{3}$ .
Conjectureopenapproximation-algorithms linear-programming tsparXiv posted 2 days ago
0 votes0 replies0 views
Dvořák–Král’–Mohar conjecture on minimum TSP walks in subcubic graphs
Dvořák–Král’–Mohar conjecture. The minimum TSP walk of $G$ has length at most
Conjectureopenapproximation-algorithms graph-theory tsparXiv posted 2 days ago

Buratti's Hamiltonian path edge-length conjecture