Skip to main content
1 of 5
Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76

Number Associated with Planar Embeddings of Hamiltonian Graphs

Is there anything known about the maximal number of simple-polygonal tours that a planar embedding of a Hamiltonian graph can have?

I am especially interested in $K_5$ and $K_{3,3}$, mainly, because due to Kuratowski's characterization of planar graphs, one can be sure that permutations of $5$, resp. $6$ cities, that correspond to the longest tour through those cities, can't appear in that order in the optimal tour through all $n$ cities; with $K_4$ that claim isn't possible.

Letting $p$ denote the maximum number of simple polygonal tours and $h$ the number of Hamiltonian tours, $h-p$ permutations of a subset of $m$ cities can be excluded from the optimal tour through all $n$ cities.

Manfred Weis
  • 13.2k
  • 4
  • 34
  • 76