2
$\begingroup$

A Halin graph is a graph constructed by embedding a tree with no vertex of degree two in the plane and then adding a cycle to join the tree’s leaves.

We found a list of the number of Halin graphs within $14$ vertices on the website https://oeis.org/A346779.

n       a(n)
1       0
2       0
3       0
4       1
5       1
6       2
7       2
8       4
9       6
10      13
11      22
12      50
13      106
14      252

It seems that there aren't many Halin graphs with at most 14 vertices (252 Halin graphs with 14 vertices is considered quite a small number).
Based on this, I estimate that the number of non-isomorphic Halin graphs within 20 vertices may also not be too large.

By Wiki, it is possible to test whether a given $n$-vertex graph is a Halin graph in linear time. To obtain Halin graphs with more vertices, such as a Halin graph with 20 vertices, one approach could be to generate 3-connected planar graphs with 20 vertices first and then filter them one by one. However, the problem is that the number of 3-connected planar graphs with 20 vertices is astronomically large. Therefore, I wonder if there is an algorithm generating Halin graphs or existing graph data available (I haven't found it either).

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

There is a theorem due to Jordan which is useful for enumerating or generating trees: every tree has a centre or a bicentre. To enumerate/generate suitable bicentral trees, enumerate/generate suitable rooted trees grouping them by height and join two rooted trees of the same height with an edge between their roots. To enumerate/generate suitable central trees, enumerate/generate suitable rooted trees grouping them by height and join two or more to the centre by their roots, ensuring that the maximum height of the trees chosen is not unique.

This construction method also gives a natural way to generate the embeddings into the plane.

Improve this answer
$\endgroup$
4
  • $\begingroup$ I'm not quite sure how your response relates to the generation of Halin graphs. I believe there are two main challenges: generating trees that meet the requirements and selecting a method to connect all the leaf nodes into a cycle (which could have multiple possible choices). $\endgroup$
    – Licheng Zhang
    Commented May 20, 2023 at 7:50
  • $\begingroup$ "Meet the requirements" = "suitable". Here the rooted trees are suitable iff no vertex has out-degree 1; for bicentral trees any two suitable rooted trees work, but for central trees the centre must connect to at least three suitable rooted trees. "Selecting a method to connect the leaf nodes into a cycle" is just embedding the tree in the plane, which is simply a question of permuting the out-edges of all the vertices in all possible ways (modulo symmetries, since e.g. a wheel graph on $n$ vertices doesn't need all $(n-1)!$ permutations of the leaves). I get 63837 Halin graphs on 20 vertices. $\endgroup$
    – Peter Taylor
    Commented May 20, 2023 at 11:51
  • $\begingroup$ Comments have been moved to chat; please do not continue the discussion here. Before posting a comment below this one, please review the purposes of comments. Comments that do not request clarification or suggest improvements usually belong as an answer, on MathOverflow Meta, or in MathOverflow Chat. Comments continuing discussion may be removed. $\endgroup$
    – Stefan Kohl ♦
    Commented May 22, 2023 at 12:10
  • $\begingroup$ I may need to extract a sentence and place it in a comment. I use permutations(self.children) to replace distinct_permutations(self.children). It is Ok but so slow. So, I believe the issue lies in the presence of sorting in the distinct_permutations function. $\endgroup$
    – Licheng Zhang
    Commented May 22, 2023 at 13:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .