Halin graph

{{multiple image

| image1 = Triangular prism as halin graph.svg

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

| alt1 = The graph of a triangular prism

| image2 = Wheel graphs.svg

| caption2 = Wheel graphs

| alt2 = Wheel graphs with four to nine vertices

| total_width = 500

}}

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.{{harvtxt|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." 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.See {{harvtxt|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.

The Frucht graph, one of the five smallest cubic graphs with no nontrivial graph automorphisms,{{citation|last1=Bussemaker|first1=F. C.|last2=Cobeljic|first2=S.|last3=Cvetkovic|first3=D. M.|last4=Seidel|first4=J. J.|publisher=Dept. of Mathematics and Computing Science, Eindhoven University of Technology|series=EUT report|title=Computer investigation of cubic graphs|journal=Eindhoven University of Technology Research Portal |url=https://research.tue.nl/en/publications/computer-investigation-of-cubic-graphs|volume=76-WSK-01|year=1976}} is also a Halin graph.{{mathworld|title=Halin Graph|id=HalinGraph|mode=cs2}}

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

| last1 = Aichholzer | first1 = Oswin

| last2 = Cheng | first2 = Howard

| last3 = Devadoss | first3 = Satyan L. | author3-link = Satyan Devadoss

| last4 = Hackl | first4 = Thomas

| last5 = Huber | first5 = Stefan

| last6 = Li | first6 = Brian

| last7 = Risteski | first7 = Andrej

| contribution = What makes a tree a straight skeleton?

| contribution-url = http://2012.cccg.ca/papers/paper30.pdf

| title = Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG'12)

| year = 2012}} 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.

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.

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.See the proof of Theorem 10 in {{citation

| last1 = Wang | first1 = Weifan

| last2 = Bu | first2 = Yuehua

| last3 = Montassier | first3 = Mickaël

| last4 = Raspaud | first4 = André

| doi = 10.1007/s10878-010-9342-6

| issue = 1

| journal = Journal of Combinatorial Optimization

| mr = 2875236

| pages = 79–93

| title = On backbone coloring of graphs

| volume = 23

| year = 2012| s2cid = 26975523

}}: "Since G contains a 3-cycle consisting of one inner vertex and two outer vertices, G is not a bipartite graph."

[[File:Halin no 8-cycle.svg|thumb|A Halin graph without any 8-cycles. A similar construction allows any single even cycle length to be avoided.{{citation

| last = Malkevitch | first = Joseph

| title = Theory and Applications of Graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976)

| chapter = Cycle lengths in polytopal graphs

| doi = 10.1007/BFb0070393

| location = Berlin

| mr = 0491287

| pages = 364–370

| publisher = Springer

| volume = 642

| year = 1978| series = Lecture Notes in Mathematics

| isbn = 978-3-540-08666-6

}}|alt=Halin graph with one 16-vertex face, two 10-vertex faces, and all other faces having 3 to 5 vertices]]

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

| last = Skowrońska | first = Mirosława

| contribution = The pancyclicity of Halin graphs and their exterior contractions

| editor1-last = Alspach | editor1-first = Brian R. | editor1-link = Brian Alspach

| editor2-last = Godsil | editor2-first = Christopher D. | editor2-link = Chris Godsil

| pages = 179–194

| publisher = Elsevier Science Publishers B.V.

| series = Annals of Discrete Mathematics

| title = Cycles in Graphs

| volume = 27

| year = 1985}}.

The incidence chromatic number of a Halin graph {{mvar|G}} with maximum degree {{math|Δ(G)}} greater than four is {{math|Δ(G) + 1}}.{{citation

| last1 = Wang | first1 = Shu-Dong

| last2 = Chen | first2 = Dong-Ling

| last3 = Pang | first3 = Shan-Chen

| doi = 10.1016/S0012-365X(01)00302-8

| issue = 1–2

| journal = Discrete Mathematics

| mr = 1927561

| pages = 397–405

| title = The incidence coloring number of Halin graphs and outerplanar graphs

| volume = 256

| year = 2002| doi-access =

}}. 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 {{math|1=Δ(G) = 3}} or {{math|4}}, the incidence chromatic number may be as large as {{math|5}} or {{math|6}} respectively.{{citation

| last1 = Shiu | first1 = W. C.

| last2 = Sun | first2 = P. K.

| doi = 10.1016/j.disc.2007.11.030

| issue = 24

| journal = Discrete Mathematics

| mr = 2466963

| pages = 6575–6580

| title = Invalid proofs on incidence coloring

| volume = 308

| year = 2008| doi-access = free

}}.

It is possible to test whether a given {{mvar|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 {{math|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.{{citation

| last1 = Fomin | first1 = Fedor V. | author1-link = Fedor Fomin

| last2 = Thilikos | first2 = Dimitrios M.

| doi = 10.1016/j.jda.2005.06.004

| issue = 4

| journal = Journal of Discrete Algorithms

| mr = 2577677

| pages = 499–510

| title = A 3-approximation for the pathwidth of Halin graphs

| volume = 4

| year = 2006| doi-access = free

}}. Alternatively, a graph with {{mvar|n}} vertices and {{mvar|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 {{math|m − n + 1}} of the graph, all of which can be checked in linear time.{{citation

| last1 = Sysło | first1 = Maciej M.

| last2 = Proskurowski | first2 = Andrzej

| contribution = On Halin graphs

| doi = 10.1007/BFb0071635

| pages = 248–256

| publisher = Springer-Verlag

| series = Lecture Notes in Mathematics

| title = Graph Theory: Proceedings of a Conference held in Lagów, Poland, February 10–13, 1981

| volume = 1018

| year = 1983}}. 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.{{citation

| last = Eppstein | first = David | authorlink = David Eppstein

| arxiv = 1502.05334

| doi = 10.7155/jgaa.00395

| issue = 2

| journal = Journal of Graph Algorithms and Applications

| pages = 323–346

| title = Simple recognition of Halin graphs and their generalizations

| volume = 20

| year = 2016| s2cid = 9525753 }}.

Every Halin graph has treewidth = 3.{{citation|title=Planar graphs with bounded treewidth|first=Hans|last=Bodlaender|authorlink=Hans L. Bodlaender|series=Technical Report RUU-CS-88-14|publisher=Department of Computer Science, Utrecht University|year=1988|url=http://archive.cs.uu.nl/pub/RUU/CS/techreps/CS-1988/1988-14.pdf|url-status=dead|archive-url=https://web.archive.org/web/20040728112030/http://archive.cs.uu.nl/pub/RUU/CS/techreps/CS-1988/1988-14.pdf|archive-date=2004-07-28}}. 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{{citation|first=Hans|last=Bodlaender|authorlink=Hans L. Bodlaender|contribution=Dynamic programming on graphs with bounded treewidth|title=Proceedings of the 15th International Colloquium on Automata, Languages and Programming|publisher=Springer-Verlag|series=Lecture Notes in Computer Science|volume=317|pages=105–118|year=1988 |doi = 10.1007/3-540-19488-6_110|hdl=1874/16258 |isbn=978-3540194880|hdl-access=free}}. or Courcelle's theorem, or in some cases (such as the construction of Hamiltonian cycles) by direct algorithms.

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

| last1 = Horton | first1 = S. B.

| last2 = Parker | first2 = R. Gary

| doi = 10.1016/0166-218X(93)E0131-H

| issue = 1

| journal = Discrete Applied Mathematics

| mr = 1311302

| pages = 19–35

| title = On Halin subgraphs and supergraphs

| volume = 56

| year = 1995| doi-access = free

}}.

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. These graphs gained significance with the discovery that many algorithmic problems that were computationally infeasible for arbitrary planar graphs could be solved efficiently on them. This fact was later explained to be a consequence of their low treewidth, and of algorithmic meta-theorems like Courcelle's theorem that provide efficient solutions to these problems on any graph of low treewidth.

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{{citation|first=Th. P.|last=Kirkman|authorlink=Thomas Kirkman|title=On the enumeration of {{mvar|x}}-edra having triedral summits and an {{math|(x − 1}})-gonal base|journal=Philosophical Transactions of the Royal Society of London|volume=146|year=1856|pages=399–411|jstor=108592|doi=10.1098/rstl.1856.0018 |doi-access=free}}. and in 1965 by Hans Rademacher. Rademacher calls these graphs based polyhedra. He defines them as the cubic polyhedral graphs with {{mvar|f}} faces in which one of the faces has {{math|f − 1}} sides.{{citation

| last = Rademacher | first = Hans | authorlink = Hans Rademacher

| journal = Illinois Journal of Mathematics

| mr = 0179682

| pages = 361–380

| title = On the number of certain types of polyhedra

| volume = 9

| issue = 3 | year = 1965| doi = 10.1215/ijm/1256068140 | doi-access = free

}}. The graphs that fit this definition are exactly the cubic Halin graphs.

Inspired by the fact that both Halin graphs and 4-vertex-connected planar graphs contain Hamiltonian cycles, {{harvtxt|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.{{citation

| last1 = Chen | first1 = Guantao

| last2 = Enomoto | first2 = Hikoe

| last3 = Ozeki | first3 = Kenta

| last4 = Tsuchiya | first4 = Shoichi

| doi = 10.1137/140971610

| issue = 3

| journal = SIAM Journal on Discrete Mathematics

| mr = 3376776

| pages = 1423–1426

| title = Plane triangulations without a spanning Halin subgraph: counterexamples to the Lovász-Plummer conjecture on Halin graphs

| volume = 29

| year = 2015}}.

The Halin graphs are sometimes also called skirted trees or roofless polyhedra.{{citation|title=Halin graphs and the travelling salesman problem|first1=G.|last1=Cornuéjols|author1-link= Gérard Cornuéjols |first2=D.|last2=Naddef|first3=W. R.|last3=Pulleyblank|author3-link=William R. Pulleyblank|journal=Mathematical Programming|volume=26|issue=3|year=1983|pages=287–294|doi=10.1007/BF02591867|s2cid=26278382}}. However, these names are ambiguous. Some authors use the name "skirted trees" to refer to planar graphs formed from trees by connecting the leaves into a cycle, but without requiring that the internal vertices of the tree have degree three or more.{{citation

| last1 = Skowrońska | first1 = M.

| last2 = Sysło | first2 = M. M.

| department = Proceedings of the International Conference on Combinatorial Analysis and its Applications (Pokrzywna, 1985)

| issue = 3–4

| journal = Zastos. Mat.

| mr = 951375

| pages = 599–610 (1988)

| title = Hamiltonian cycles in skirted trees

| volume = 19

| year = 1987}} And like "based polyhedra", the "roofless polyhedra" name may also refer to the cubic Halin graphs.{{citation

| last1 = Lovász | first1 = L. | author1-link = László Lovász

| last2 = Plummer | first2 = M. D. | author2-link = Michael D. Plummer

| contribution = On a family of planar bicritical graphs

| location = London

| mr = 0351915

| pages = 103–107. London Math. Soc. Lecture Note Ser., No. 13

| publisher = Cambridge Univ. Press

| title = Combinatorics (Proc. British Combinatorial Conf., Univ. Coll. Wales, Aberystwyth, 1973)

| year = 1974}}. The convex polyhedra whose graphs are Halin graphs have also been called domes.{{citation|contribution=Zipper unfolding of domes and prismoids|first1=Erik D.|last1=Demaine|author1-link=Erik Demaine|first2=Martin L.|last2=Demaine|author2-link=Martin Demaine|first3=Ryuhei|last3=Uehara|title=Proceedings of the 25th Canadian Conference on Computational Geometry (CCCG 2013), Waterloo, Ontario, Canada, August 8–10, 2013|pages=43–48|year=2013|url=http://erikdemaine.org/papers/ZipperDomes_CCCG2013/}}.

{{reflist|30em}}

• [http://www.graphclasses.org/classes/gc_198.html Halin graphs], Information System on Graph Class Inclusions.

Category:Graph families

Category:Planar graphs