Halin graph

In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of its edges cross (this is called planar embedding), and the cycle connects the leaves in their clockwise ordering in this embedding. Thus, the cycle forms the outer face of the Halin graph, with the tree inside it.

Halin graphs are named after German mathematician Rudolf Halin, who studied them in 1971, but the cubic Halin graphs – the ones in which each vertex touches exactly three edges – had already been studied over a century earlier by Kirkman. They are polyhedral graphs, meaning that every Halin graph can be used to form the vertices and edges of a convex polyhedron, and the polyhedra formed from them have been called roofless polyhedra or domes.

Every Halin graph has a Hamiltonian cycle through all its vertices, as well as cycles of almost all lengths up to their number of vertices. The Halin graphs can be recognized in linear time. Many computational problems that are hard on other kinds of planar graphs, such as finding Hamiltonian cycles, can also be solved quickly on Halin graphs.

A star is a tree with exactly one internal vertex. Applying the Halin graph construction to a star produces a wheel graph, the graph of the (edges of) a pyramid. The graph of a triangular prism is also a Halin graph: it can be drawn so that one of its rectangular faces is the exterior cycle, and the remaining edges form a tree with four leaves, two interior vertices, and five edges.

...
Wikipedia