Halin graph
From Wikipedia, the free encyclopedia
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 a 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.[1]
Halin graphs are named after German mathematician Rudolf Halin, who studied them in 1971.[2] The cubic Halin graphs – the ones in which each vertex touches exactly three edges – had already been studied over a century earlier by Kirkman.[3] Halin graphs 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 the number of vertices of the graph. Halin graphs can be recognized in linear time. Because Halin graphs have low treewidth, many computational problems that are hard on other kinds of planar graphs, such as finding Hamiltonian cycles, can 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.[4] 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.[5]
The Frucht graph, one of the five smallest cubic graphs with no nontrivial graph automorphisms,[6] is also a Halin graph.[7]
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. The polyhedron that realizes the graph can be chosen so that the face containing all of the tree leaves is horizontal, and all of the other faces lie above it, with equal slopes.[8] As with every polyhedral graph, Halin graphs have a unique planar embedding, 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 the deletion of any vertex.[9] 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.[10]
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.[12]
The incidence chromatic number of a Halin graph G with maximum degree Δ(G) greater than four is Δ(G) + 1.[13] This is the number of colors needed to color all pairs (v,e) where v is a vertex of the graph, and e is an edge incident to v, obeying certain constraints on the coloring. Pairs that share a vertex or that share an edge are not allowed to have the same color. In addition, a pair (v,e) cannot have the same color as another pair that uses the other endpoint of e. For Halin graphs with Δ(G) = 3 or 4, the incidence chromatic number may be as large as 5 or 6 respectively.[14]
The numbers of different Halin graphs on vertices, starting at (the smallest possible), are:[15]
- 1, 1, 2, 2, 4, 6, 13, 22, 50, 106, 252, 589, 1475, 3669, 9435, 24345, ...
This enumeration counts two embedded Halin graphs as the same when they are mirror reflections of each other. When reflections of asymmetric Halin graphs are counted as distinct, the numbers become[16]
- 1, 1, 2, 2, 4, 7, 16, 32, 76, 181, 443, 1098, 2793, 7127, 18458, 48128, ...
Computational complexity
It is possible to test whether a given n-vertex graph is a Halin graph in linear time, by finding a planar embedding of the graph (if one exists), and then testing whether there exists a face that has at least n/2 + 1 vertices, all of degree three. If so, there can be at most four such faces, and it is possible to check in linear time for each of them whether the rest of the graph forms a tree with the vertices of this face as its leaves. On the other hand, if no such face exists, then the graph is not Halin.[17] Alternatively, a graph with n vertices and m edges is Halin if and only if it is planar, 3-connected, and has a face whose number of vertices equals the circuit rank m − n + 1 of the graph, all of which can be checked in linear time.[18] Other methods for recognizing Halin graphs in linear time include the application of Courcelle's theorem, or a method based on graph rewriting, neither of which rely on knowing the planar embedding of the graph.[19]
Every Halin graph has treewidth = 3.[20] 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[21] or Courcelle's theorem, or in some cases (such as the construction of Hamiltonian cycles) by direct algorithms.[19] However, it is NP-complete to find the largest Halin subgraph of a given graph, to test whether there exists a Halin subgraph that includes all vertices of a given graph, or to test whether a given graph is a subgraph of a larger Halin graph.[22]