Graphe de Halin

Le graphe des arêtes d'un prisme triangulaire vu comme un graphe de Halin. L'arbre central est en bleu et le cycle extérieur est en noir.

Les graphes roue (les graphes des arêtes d'une pyramide) sont des graphes de Halin ; leur arbre est un graphe étoile.

Le graphe des arêtes d'un prisme triangulaire est également un graphe de Halin (figure).

Le graphe de Frucht, un des plus petits graphes cubiques sans automorphisme de graphe trivial, est aussi un graphe de Halin.

• Tout graphe de Halin est un graphe planaire au nombre minimal d'arêtes qui est 3-connexe[1]. Le théorème de Steinitz (en) permet d'en déduire que c'est un graphe polyédrique.
• Tout graphe de Halin a un plongement (en) planaire unique, au choix près de l’espace extérieur, c'est-à-dire un unique plongement dans une 2-sphère[1].
• Tout graphe de Halin est hamiltonien, et chaque arête du graphe appartient à un cycle hamiltonien. De plus, un graphe de Halin reste hamiltonien lorsque l'on supprime n'importe quel sommet[4].
• Tout graphe de Halin est presque pancyclique, dans le sens où il comporte des cycles de toutes les longueurs de ${\displaystyle 3}$ à ${\displaystyle n}$ (le nombre de sommets) sauf éventuellement une unique longueur paire. De plus, un graphe de Halin reste presque pancyclique si une seule arête est contractée. Enfin, un graphe de Halin sans sommets intérieurs de degré 3 est pancyclique[5].
• Tout graphe de Halin a une largeur arborescente inférieure ou égale à 3[6]. Par conséquent, beaucoup de problèmes qui sont NP-complets dans le cas général, comme la recherche d'un stable de taille maximum, peuvent être résolus en durée linéaire dans le cas des graphes de Halin en s'appuyant sur de la programmation dynamique[7].
• Tout graphe de Halin contient un triangle. En effet, chaque arbre sans sommets de degré 2 contient au moins deux feuilles qui partagent le même parent. En particulier, un graphe de Halin ne peut par être un graphe sans triangle ni un graphe biparti.
• Le dual faible d'un graphe de Halin est biconnexe et planaire extérieur. Un graphe planaire est un graphe de Halin si et seulement si son dual faible est biconnexe et planaire extérieur[8].

En 1971, Halin a introduit les graphes de Halin comme une sorte de graphes au moins 3-connexes, en faisant remarquer que la suppression de n'importe quelle arête du graphe changeait le degré de connexité du graphe. Ces graphes ont gagné en importance lorsque l'on a découvert que de nombreux problèmes algorithmiques qui étaient difficiles à résoudre par calcul pour des graphes planaires arbitraires pouvaient être résolus efficacement avec eux[4] - [8], une propriété qui a été expliquée plus tard comme une conséquence de leur faible largeur arborescente[6] - [7].

Avant les travaux de Halin sur ces graphes, des problèmes d'énumération de graphes (en) concernant les graphes de Halin cubiques ont été étudiés en 1965 par Hans Rademacher[9]. Rademacher définit ces graphes (qu'il appelle based polyhedra, polyèdres à base) comme les graphes polyédriques cubiques dans lesquels une des faces comporte ${\displaystyle f-1}$ côtés, où ${\displaystyle f}$ est le nombre de faces du polyèdre. Il mentionne lui-même des travaux bien antérieurs publiés en 1856 par Thomas Kirkman sur la même classe de graphes[3]

Les graphes de Halin sont parfois également appelés roofless polyhedra (polyèdres à ciel ouvert)[4], mais, comme based polyhedra, ce nom peut aussi faire référence aux graphes de Halin cubiques[10].

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Halin graph » (voir la liste des auteurs).

• (en) Halin graph, Information System on Graph Class Inclusions.
• (en) Eric W. Weisstein, « Halin Graph », sur MathWorld