Skip to main content
MathOverflow

Return to Question

edited title
Link
Licheng Zhang
Licheng Zhang
  • 1.9k
  • 6
  • 17

Is there an algorithm to generate non-isomorphic Halin graphs?

edited tags
Source Link
Licheng Zhang
Licheng Zhang
  • 1.9k
  • 6
  • 17

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).

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).

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).

Source Link
Licheng Zhang
Licheng Zhang
  • 1.9k
  • 6
  • 17

Is there an algorithm to generate Halin graphs?

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).