Halin graph

From formulasearchengine
Jump to navigation Jump to search
A Halin graph.

In graph theory, a Halin graph is a type of planar graph. It is constructed from a tree that has at least four vertices, none of which have exactly two neighbors. The tree is drawn in the plane so none of its edges cross; then edges are added that connect all its leaves into a cycle.[1] Halin graphs are named after German mathematician Rudolf Halin, who studied them in 1971,[2] but the cubic Halin graphs had already been studied over a century earlier by Kirkman.[3]

Construction

A triangular prism, constructed as a Halin graph from a six-vertex tree

A Halin graph is constructed as follows. Let be a tree with more than three vertices, such that no vertex of has degree two (that is, no vertex has exactly two neighbors), embedded in the plane. Then a Halin graph is constructed by adding to a cycle through each of its leaves, such that the augmented graph remains planar.

Examples

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

The Frucht graph, one of the two smallest cubic graphs with no nontrivial graph automorphisms, is also a Halin graph.

Properties

Every Halin graph is 3-connected, meaning that it is not possible to delete two vertices from it and disconnect the remaining vertices. It is edge-minimal 3-connected, meaning that if any one of its edges is removed, the remaining graph will no longer be 3-connected.[1] By Steinitz's theorem, as a 3-connected planar graph, it can be represented as the set of vertices and edges of a convex polyhedron; that is, it is a polyhedral graph. And, as with every polyhedral graph, its planar embedding is unique up to the choice of which of its faces is to be the outer face.[1]

Every Halin graph is a Hamiltonian graph, and every edge of the graph belongs to a Hamiltonian cycle. Moreover, any Halin graph remains Hamiltonian after deletion of any vertex.[4] Because every tree without vertices of degree 2 contains two leaves that share the same parent, every Halin graph contains a triangle. In particular, it is not possible for a Halin graph to be a triangle-free graph nor a bipartite graph. More strongly, every Halin graph is almost pancyclic, in the sense that it has cycles of all lengths from 3 to n with the possible exception of a single even length. Moreover, any Halin graph remains almost pancyclic if a single edge is contracted, and every Halin graph without interior vertices of degree three is pancyclic.[5]

Every Halin graph has treewidth at most three.[6] Therefore, many graph optimization problems that are NP-complete for arbitrary planar graphs, such as finding a maximum independent set, may be solved in linear time on Halin graphs using dynamic programming.[7]

The weak dual of an embedded planar graph has vertices corresponding to bounded faces of the planar graph, and edges corresponding to adjacent faces. The weak dual of a Halin graph is always biconnected and outerplanar. This property may be used to characterize the Halin graphs: an embedded planar graph is a Halin graph, with the leaf cycle of the Halin graph as the outer face of the embedding, if and only if its weak dual is biconnected and outerplanar.[8]

History

In 1971, Halin introduced the Halin graphs as a class of minimally 3-vertex-connected graphs: for every edge in the graph, the removal of that edge reduces the connectivity of the graph.[2] These graphs gained in significance with the discovery that many algorithmic problems that were computationally infeasible for arbitrary planar graphs could be solved efficiently on them,[4][8] a fact that was later explained to be a consequence of their low treewidth.[6][7]

Prior to Halin's work on these graphs, graph enumeration problems concerning the cubic Halin graphs were studied in 1856 by Thomas Kirkman[3] and in 1965 by Hans Rademacher.[9] Rademacher calls these graphs based polyhedra. He defines them as the cubic polyhedral graphs with f faces in which one of the faces has f − 1 sides. The graphs that fit this definition are exactly the cubic Halin graphs.

The Halin graphs are sometimes also called roofless polyhedra,[4] but, like "based polyhedra", this name may also refer to the cubic Halin graphs.[10] The convex polyhedra whose graphs are Halin graphs have also been called domes.[11]

References

  1. 1.0 1.1 1.2 Encyclopaedia of Mathematics, first Supplementary volume, 1988, ISBN 0-7923-4709-9, p. 281, article "Halin Graph", and references therein.
  2. 2.0 2.1 {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  3. 3.0 3.1 {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  4. 4.0 4.1 4.2 {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  5. {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  6. 6.0 6.1 {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  7. 7.0 7.1 {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  8. 8.0 8.1 {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  9. {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  10. {{#invoke:citation/CS1|citation |CitationClass=citation }}.
  11. {{#invoke:citation/CS1|citation |CitationClass=citation }}.

External links