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.

  • $\begingroup$ another example of those graphs is the union of a strictly convex polygon with its Voronoi diagram $\endgroup$ – Manfred Weis Mar 28 '18 at 12:52
  • 1
    $\begingroup$ How about “Halin graph”? $\endgroup$ – Gordon Royle Mar 28 '18 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 '18 at 14:01

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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