Timeline for Is there an algorithm to generate non-isomorphic Halin graphs?
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 22, 2023 at 13:14 | comment | added | Licheng Zhang |
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.
|
|
| S May 22, 2023 at 12:10 | history | mod moved comments to chat | |||
| S May 22, 2023 at 12:10 | comment | added | Stefan Kohl♦ | 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. | |
| May 20, 2023 at 14:05 | vote | accept | Licheng Zhang | ||
| May 20, 2023 at 11:51 | comment | added | Peter Taylor | "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. | |
| May 20, 2023 at 7:50 | comment | added | Licheng Zhang | 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). | |
| May 19, 2023 at 8:59 | history | answered | Peter Taylor | CC BY-SA 4.0 |