4

Halin graphs contain a Hamilton cycle and have the interesting property, that, also in the case of arbitrary real edge weights, it is possible to report one of the shortest contained Hamilton cycles in $O(n)$ time ("G. Cornuejols, D. Naddef, and W.R. Pulleyblank. Halin graphs and the travelling salesman problem. Mathematical Programming, 26:287–294, 1983." or this answer ), and I would like to know, for which kind of Halin graphs the savings over enumerating all Hamilton cycles is maximal.

Question:
given the number $n$ of vertices, what is the maximal number of Hamilton cycles that Halin graphs can contain and what are examples of such extremal Halin graphs?

Manfred Weis
  • 12,594
  • 4
  • 34
  • 71
  • What does "shortest Hamiltonian cycle" mean in this context? Gerhard "Aren't They All The Same?" Paseman, 2018.08.17. – Gerhard Paseman Aug 17 '18 at 19:21
  • @GerhardPaseman the question for the shortest Hamilton cycle implies that the length of the cycles equals the sum of their edge lengths, and the edge lengths can be arbitrary real values. I admit that the formulation should have been "one of the shortest Hamilton cycles" instead of "the shortest Hamilton cycle"; I'll edit accordingly. – Manfred Weis Aug 17 '18 at 20:31
  • 1
    Then don't hide the weights; make them explicit. I am seeing no mention of weighted edges in the linked article or in your post. (The title of the cited article gives a clue, but readers are not always drawing the desired inferences.). Gerhard "Clarity And Explicitness Above All" Paseman, 2018.08.17. – Gerhard Paseman Aug 17 '18 at 20:39
  • 2
    All Halin graphs are polyhedral graphs. So you might be interested in the earlier MO question, Why are there 1024 Hamiltonian cycles on an icosahedron?, which was nicely answered by @EdWynn. To jump to the answer: It seems likely to be something of a numerical accident. – Joseph O'Rourke Aug 17 '18 at 23:56
  • @JosephO'Rourke indeed, Halin graphs have the property that there one face, namely the one defined by the tour through the leaves of a spanning tree, which makes them a special subset of the polyhedral graph, i.e. of the roofless polyhedra and thus, what applies to the hamiltonicity of polyhedral graphs also applies to Halin graphs. In that respect the techniques for determining the number of Hamilton cycles in the icosahedron are a good hint for further attempts to come up with better estimates for Halin graphs. – Manfred Weis Aug 18 '18 at 10:50
  • The paper to which you refer gives a construction of Halin graphs on $4k+1$ vertices with exponentially many Hamilton cycles.

    Start with a star $K_{1,k}$ and to each leaf of the star attach three new vertices, which will be leaves of the "tree-part" of the Halin graph.

    Join these $3k$ leaves in a cycle in the obvious fashion forming the "cycle part" of the Halin graph.

    These graphs have $k \times 2^{k-2}$ Hamilton cycles, and I would not be surprised if they are the long-term winners. But for small numbers of vertices they are not the best.

     – Gordon Royle Aug 20 '18 at 07:19

0 Answers0