Skip to main content
3 of 5
Did some copy-editing. Style of question preserved. Gist of the question seems still not clear. Refrained from trying to sharpen the question.

Number Associated with Planar Embeddings of Hamiltonian Graphs

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

Remarks.

  • 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, i.e. those permutations which correspond to a Hamilton circuit, can't appear in that order in the optimal tour through all $n$ cities; with $K_4$, this is not so.

  • 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