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
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
Every Halin graph has a
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 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
Every Halin graph is a
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]
Computational complexity
It is possible to test whether a given n-vertex graph is a Halin graph in
Every Halin graph has
History
In 1971, Halin introduced the Halin graphs as a class of
Prior to Halin's work on these graphs, graph enumeration problems concerning the cubic (or 3-regular) Halin graphs were studied in 1856 by Thomas Kirkman[3] and in 1965 by Hans Rademacher. 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.[21] The graphs that fit this definition are exactly the cubic Halin graphs.[22]
Inspired by the fact that both Halin graphs and 4-vertex-connected planar graphs contain Hamiltonian cycles, Lovász & Plummer (1974) conjectured that every 4-vertex-connected planar graph contains a spanning Halin subgraph; here "spanning" means that the subgraph includes all vertices of the larger graph. The Lovász–Plummer conjecture remained open until 2015, when a construction for infinitely many counterexamples was published.[23]
The Halin graphs are sometimes also called skirted trees
References
- ^ ISBN 0-7923-4709-9, p. 281, article "Halin Graph", and references therein.
- ^ MR 0278980.
- ^ JSTOR 108592.
- ^ Cornuéjols, Naddef & Pulleyblank (1983): "If T is a star, i.e., a single node v joined to n other nodes, then H is called a wheel and is the simplest type of Halin graph."
- ^ See Sysło & Proskurowski (1983), Prop. 4.3, p. 254, which identifies the triangular prism as the unique graph with exactly three cycles that can be the outer cycle of a realization as a Halin graph.
- ^ Bussemaker, F. C.; Cobeljic, S.; Cvetkovic, D. M.; Seidel, J. J. (1976), "Computer investigation of cubic graphs", Eindhoven University of Technology Research Portal, EUT report, 76-WSK-01, Dept. of Mathematics and Computing Science, Eindhoven University of Technology
- ^ Weisstein, Eric W., "Halin Graph", MathWorld
- ^ Aichholzer, Oswin; Cheng, Howard; Devadoss, Satyan L.; Hackl, Thomas; Huber, Stefan; Li, Brian; Risteski, Andrej (2012), "What makes a tree a straight skeleton?" (PDF), Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG'12)
- ^ S2CID 26278382.
- S2CID 26975523: "Since G contains a 3-cycle consisting of one inner vertex and two outer vertices, G is not a bipartite graph."
- ^ MR 0491287
- ^ Skowrońska, Mirosława (1985), "The pancyclicity of Halin graphs and their exterior contractions", in Alspach, Brian R.; Godsil, Christopher D. (eds.), Cycles in Graphs, Annals of Discrete Mathematics, vol. 27, Elsevier Science Publishers B.V., pp. 179–194.
- MR 1927561.
- MR 2466963.
- MR 2577677.
- ^ .
- ^ S2CID 9525753.
- ^ a b Bodlaender, Hans (1988), Planar graphs with bounded treewidth (PDF), Technical Report RUU-CS-88-14, Department of Computer Science, Utrecht University, archived from the original (PDF) on 2004-07-28.
- ^ ISBN 978-3540194880.
- MR 1311302.
- MR 0179682.
- ^ MR 0351915.
- MR 3376776.
- MR 0951375
- ^ Demaine, Erik D.; Demaine, Martin L.; Uehara, Ryuhei (2013), "Zipper unfolding of domes and prismoids", Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013), Waterloo, Ontario, Canada, August 8–10, 2013, pp. 43–48.
External links
- Halin graphs, Information System on Graph Class Inclusions.