Graphe pancyclique

En théorie des graphes, un graphe pancyclique est un graphe qui contient des cycles de toutes les longueurs de trois jusqu'au nombre de sommets du graphe. Les graphes pancycliques sont une généralisation des graphes hamiltoniens qui ont un cycle qui passe par tous les sommets.

Cycles de longueurs 3,4,5 et 6 dans le graphe d'un octaèdre, montrant qu'il est pancyclique.

Définitions

Un graphe $G$ à $n$ sommets est pancyclique si, pour tout entier $k$ avec $3\leq k\leq n$, le graphe contient un cycle de longueur $k$. Il est nœud-pancyclique ou sommet-pancyclique si, pour chaque sommet $s$ et tout $k$ avec $3\leq k\leq n$, il contient un cycle de longueur $k$ qui passe par $s$. De même, il est arête-pancyclique si, pour chaque arête $a$ et tout $k$, il contient un cycle de longueur $k$ qui utilise $a$.

Un graphe biparti ne peut pas être pancyclique, car il ne contient aucun cycle de longueur impaire, mais il est dit bipancyclique s'il contient des cycles de toutes les longueurs paires de 4 à n.

Le nombre de graphes pancycliques à $n=0,1,\ldots$ sommets est 0, 0, 1, 2, 7, 43, 372, 6132, 176797, 9302828, ... (suite A286684 de l'OEIS).

Graphes planaires

Un graphe planaire extérieur maximal est par définition un graphe formé par un polygone simple du plan en triangulant son intérieur. Un graphe planaire extérieur maximal est pancyclique, comme on peut le montrer par induction. La face externe du graphe est un cycle de longueur n, et la suppression d'un triangle connecté au reste du graphe par une seule arête (une feuille de l'arbre qui forme le graphe dual de la triangulation) forme un graphe planaire extérieur maximal sur un sommet de moins, graphe qui par induction a des cycles de toutes les longueurs restantes. En choisissant convenablement le triangle à supprimer, le même argument montre en plus qu'un graphe planaire extérieur maximal est nœud-pancyclique. Il en est de même pour les graphes qui ont un sous-graphe couvrant planaire extérieur maximal, comme c'est le cas par exemple pour les graphes roue.

Un graphe planaire maximal est un graphe planaire dans lequel toutes les faces, même la face extérieure, sont des triangles. Un graphe planaire maximal est nœud-pancyclique si et seulement s'il a un cycle hamiltonien en effet : s'il n'est pas hamiltonien, il n'est certainement pas pancyclique, et s'il est hamiltonien, alors l'intérieur du cycle hamiltonien forme un graphe planaire extérieur maximal sur les mêmes nœuds, auquel l'argument précédent pour les graphes planaires extérieurs maximaux s'applique. Par exemple, l'illustration montre la pancyclicité du graphe d'un octaèdre, un graphe planaire maximal hamiltonien à six sommets. Par le même argument, si un graphe planaire maximal a un cycle de longueur k, il a des cycles de toutes les longueurs plus petites.

Un graphe de Halin presque pancyclique, avec des cycles de toutes longueurs jusqu'à n sauf de longueur 8.

Les graphes de Halin sont les graphes planaires formés à partir d'une représentation planaire d'un arbre qui n'a pas de sommet de degré deux, en ajoutant un cycle qui relie toutes les feuilles de l'arbre. Les graphes de Halin ne sont pas nécessairement pancycliques, mais ils sont presque pancycliques en ce sens qu'il manque au plus une longueur de cycle. La longueur du cycle manquant est nécessairement paire. Si aucun des sommets intérieurs d'un graphe de Halin n'a de degré trois, alors il est nécessairement pancyclique.

Bondy (1971) a observé que de nombreuses conditions usuelles pour l'existence d'un cycle hamiltonien étaient également des conditions suffisantes pour qu'un graphe soit pancyclique, et sur cette base il a conjecturé que tout graphe planaire à 4-connexe est pancyclique. Malkevitch (1971) a trouvé une famille de contre-exemples.

Tournois

Un tournoi est un graphe orienté avec un arc entre chaque paire de sommets. Intuitivement, un tournoi peut être utilisé pour modéliser un tournoi toutes rondes, en traçant un arc du gagnant vers le perdant dans chaque match de la compétition. Un tournoi est dit fortement connexe ou fort si et seulement s'il ne peut pas être partitionné en deux sous-ensembles non vides P et G de perdants et de gagnants, tels que chaque concurrent de G bat chaque concurrent de P. Un tournoi fort est pancyclique et nœud-pancyclique. Si un tournoi est régulier (chaque concurrent a le même nombre de victoires et de défaites que chaque autre concurrent), alors il est également pancyclique ; cependant, un tournoi fort avec quatre sommets ne peut pas être arête-pancyclique.

Graphes pleins

Le théorème de Turán stipule que tout graphe non orienté à $n$ sommets avec au moins $n^{2}/4$ arêtes, et sans arêtes multiples ou boucles, contient soit un triangle, soit le graphe biparti complet $K_{n/2,n/2}$. Ce théorème peut être précisé : tout graphe hamiltonien non orienté avec au moins $n^{2}/4$ arêtes arêtes est soit pancyclique soit égal à $K_{n/2,n/2}$.

Il existe des graphes orientés hamiltoniens à $n$ sommets avec $n(n+1)/2-3$ arcs qui ne sont pas pancycliques, mais un graphe orienté hamiltonien avec au moins $n(n+1)/2-1$ arcs est pancyclique. De plus, tout graphe orienté à $n$ sommets fortement connexe dans lequel chaque sommet est de degré au moins $n$ (en comptant les arêtes entrantes et les sortantes) est soit pancyclique, soit un graphe orienté bipartite complet.

Puissances de graphes

Pour tout graphe $G$, la $k$-ième puissance $G^{k}$ est définie comme le graphe sur le même ensemble de sommets qui a une arête entre deux sommets dont la distance dans $G$ est au plus $k$. Si $G$ est sommet-connexe, alors d'après le théorème de Fleischner son carré $G^{2}$ est hamiltonien ; on peut montrer qu'il est nécessairement sommet-pancyclique. Plus généralemment, si $G^{2}$ est hamiltonien, il est également pancyclique.

Complexité algorithmique

Il est NP-complet de tester si un graphe est pancyclique, même dans le cas particulier des graphes cubiques 3-connexes, et il est aussi NP-complet de tester si un graphe est sommet-pancyclique, même dans le cas particulier des graphes polyédriques. Il est également NP-complet de tester si le carré d'un graphe est hamiltonien, et donc s'il est pancyclique.

Historique

Les graphes pancycliques ont été étudiés pour la première fois dans le contexte des tournois par Harary et Moser (1966), Moon (1966) et Alspach (1967)). Le concept de pancyclicité a été nommé et étendu aux graphes non orientés par Bondy. Un travail plus récent est la thèse de Zengxian Tian.

Notes et références

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

Liens externes

• (en) Eric W. Weisstein, « Pancyclic Graph », sur MathWorld