4
$\begingroup$

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?

Improve this question
$\endgroup$
6
  • $\begingroup$ What does "shortest Hamiltonian cycle" mean in this context? Gerhard "Aren't They All The Same?" Paseman, 2018.08.17. $\endgroup$
    – Gerhard Paseman
    Commented Aug 17, 2018 at 19:21
  • $\begingroup$ @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. $\endgroup$
    – Manfred Weis
    Commented Aug 17, 2018 at 20:31
  • 1
    $\begingroup$ 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. $\endgroup$
    – Gerhard Paseman
    Commented Aug 17, 2018 at 20:39
  • 2
    $\begingroup$ 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. $\endgroup$
    – Joseph O'Rourke
    Commented Aug 17, 2018 at 23:56
  • $\begingroup$ @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. $\endgroup$
    – Manfred Weis
    Commented Aug 18, 2018 at 10:50

0

Reset to default

You must log in to answer this question.