3
$\begingroup$

Is there an established name for graphs, that can be decomposed into

  • a tree with at least three leaf nodes and
  • a connected two-regular graph with the tree's leaf nodes as vertices?

examples of those graphs are the edge-graphs of polyhedra with one facet, that is edge-adjacent to all other facets.

Improve this question
$\endgroup$
3
  • $\begingroup$ another example of those graphs is the union of a strictly convex polygon with its Voronoi diagram $\endgroup$
    – Manfred Weis
    Mar 28, 2018 at 12:52
  • 1
    $\begingroup$ How about “Halin graph”? $\endgroup$
    – Gordon Royle
    Mar 28, 2018 at 13:18
  • $\begingroup$ @GordonRoyle yes, that fits; Wolfram makes the restriction, that there be no nodes of degree 2, but that isn't an essential restriction. It would be an acceptable answer to my question. $\endgroup$
    – Manfred Weis
    Mar 28, 2018 at 14:01

1 Answer 1

Reset to default
4
$\begingroup$

Ok, since it is close enough for the OP (as evidenced by the comments) I will transfer my comment to an answer so that the question can be neatly wrapped up.

So a Halin graph (named after Rudolf Halin) is built from a tree with no vertices of degree 2 that is embedded in the plane and whose leaves are then connected in a cycle determined by the embedding.

So the OP's class of graphs (which permits vertices of degree 2) is a Halin graph with some tree-edges subdivided.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.