Famille de Petersen

La famille de Petersen. Le graphe complet K₆ est en haut de l'illustration, et le graphe de Petersen est en bas. Les liaisons bleues indiquent des transformations Δ-Y ou Y-Δ entre les graphe s de la famille.

En mathématiques, et plus précisément en théorie des graphes, la famille de Petersen est un ensemble de sept graphes non orientés contenant le graphe de Petersen et le graphe complet K₆. Cette famille a été découverte et étudiée par le mathématicien danois Julius Petersen.

Définition

La forme des transformations Δ-Y et Y-Δ utilisée pour définir la famille de Petersen est la suivante :

• Si un graphe G contient un sommet s ayant exactement trois voisins (donc trois arêtes partant de lui), la transformation Y-Δ de G en s est le graphe obtenu en supprimant s (et les trois arêtes qui en partent) de G et en ajoutant une nouvelle arête entre chaque couple de voisins de s.
• Si un graphe H contient un triangle rst, la transformation Δ-Y de H en rst est le graphe formé en supprimant les arêtes rs, st, et rt de H, et en ajoutant un nouveau sommet x et les trois arêtes rx, sx et tx.

(le nom de ces transformations provient de la forme en Δ d'un triangle du graphe, et de la forme en Y d'un sommet de degré 3). Bien que ces opérations puissent en principe conduire à des multigraphes, cela ne se produit pas pour les graphes de la famille de Petersen. Ces transformations conservant le nombre d'arêtes d'un graphe, on ne peut, en les utilisant, construire qu'un nombre fini de graphes (ou de multigraphes) à partir d'un graphe initial donné.

La famille de Petersen est définie comme l'ensemble des graphes qui peuvent être atteint à partir du graphe de Petersen par combinaison de transformations Δ-Y et Y-Δ. Parmi les sept graphes de la famille, outre le graphe de Petersen, on trouve le graphe complet K₆ à six sommets, le graphe à huit sommets obtenu en supprimant une arête du graphe biparti complet K_4,4, et le graphe complet triparti à sept sommets K_3,3,1.

Mineurs exclus

Articles détaillés : Mineur (théorie des graphes) et Théorème de Robertson-Seymour.

Le graphe apical irréductible de Robertson, démontrant que les graphes YΔY-réductibles ont d'autres mineurs exclus que ceux de la famille de Petersen.

Un mineur d'un graphe G est un autre graphe formé à partir de G en contractant et en supprimant des arêtes. Le théorème de Robertson-Seymour montre que de nombreuses familles de graphes peuvent être caractérisées par un ensemble fini de mineurs exclus : ainsi, d'après le théorème de Wagner, les graphes planaires sont ceux n'ayant comme mineurs ni le graphe completK₅, ni le graphe biparti complet K_3,3.

Neil Robertson, Paul Seymour et Robin Thomas (en) utilisèrent la famille de Petersen pour caractériser de même les graphes plongeables dans l'espace usuel sans entrelacements, définis comme étant les plongements tels que tout cycle du graphe soit la frontière d'un disque non traversé par le reste du graphe^[1]. Horst Sachs (en) avait déjà étudié ces plongements, montré que les sept graphes de la famille de Petersen ne pouvaient être ainsi plongés, et posé la question de caractériser les graphes plongeables sans entrelacements par une famille de mineurs exclus^[2]. Robertson et al. résolurent cette question en montrant que la famille de Petersen constituait exactement l'ensemble des mineurs exclus recherché.

La famille de Petersen est aussi contenue dans l'ensemble des mineurs exclus pour une autre famille de graphes fermée pour les mineurs, la famille des graphes YΔY-réductibles. Un graphe connexe est YΔY-réductible s'il peut être réduit à un seul sommet par une succession de transformations Δ-Y ou Y-Δ, de suppressions de boucles ou d'arêtes multiples, de suppression de sommets n'ayant qu'un voisin, et de remplacements d'un sommet ayant exactement deux voisins par une arête les reliant. Ainsi, le graphe complet K₄ peut être réduit à un seul sommet par la séquence : la transformation Y-Δ qui en fait un triangle à côtés doubles, la suppression de ces trois côtés doubles, la transformation Δ-Y l'amenant au graphe en Y K_1,3, et la suppression des trois sommets simples. Chacun des graphes de la famille de Petersen est un mineur exclus minimal pour la famille des graphes YΔY-réductibles^[3].

Cependant, Neil Robertson a donné un exemple, montré ci-contre, d'un graphe apical (en) (un graphe obtenu en ajoutant un sommet à un graphe planaire, et donc clairement plongeable sans entrelacements) qui n'est pas YΔY-réductible, montrant que les graphes YΔY-réductibles forment un sous-ensembles strict des graphes plongeables sans entrelacements, et donc possèdent un ensemble de mineurs exclus plus vaste que la famille de Petersen^[3]. En fait, Yaming Yu a montré en 2006 qu'il y avait au moins 68 897 913 652 mineurs exclus pour cette famille^[4].

Notes

1. ↑ Cette définition est plus forte que celle correspondant à la version usuelle, demandant que deux cycles quelconques soient non entrelacés, puisqu'elle exclut également les entrelacs brunniens ; voir Robertson, Seymour et Thomas 1993.
2. ↑ (en) Horst Sachs, Graph Theory: Proceedings of a Conference held in Łagów, Poland, February 10–13, 1981, vol. 1018, Springer-Verlag, 1983, 230–241 p. .
3. ↑ ^{a et b} (en) Klaus Truemper, Matroid Decomposition, Academic Press, 1992, 100–101 p. [lire en ligne] .
4. ↑ (en) Yaming Yu, « More forbidden minors for wye-delta-wye reducibility », dans Electronic Journal of Combinatorics, vol. 13, n^o 1, 2006, p. #R7 [texte intégral] .

Références

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

• (en) Neil Robertson, P. D. Seymour et Robin Thomas, « Linkless embeddings of graphs in 3-space », dans Bulletin of the American Mathematical Society, vol. 28, n^o 1, 1993, p. 84–89 [texte intégral] .

Voir aussi

• Graphe de Petersen

• Théorème de Robertson-Seymour