Graphe pancyclique

Cycles de longueurs 3,4,5 et 6 dans le graphe d'un octaèdre, montrant qu'il est 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.

Définitions

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

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^[3].

Le nombre de graphes pancycliques à ${\displaystyle 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^[4]. 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^[5] 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^[6]. 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^[7].

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^[8].

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^[9]. Un tournoi fort est pancyclique^[10] et nœud-pancyclique^[11]. 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^[12] ; 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é à ${\displaystyle n}$ sommets avec au moins ${\displaystyle n^{2}/4}$ arêtes, et sans arêtes multiples ou boucles, contient soit un triangle, soit le graphe biparti complet ${\displaystyle K_{n/2,n/2}}$. Ce théorème peut être précisé : tout graphe hamiltonien non orienté avec au moins ${\displaystyle n^{2}/4}$ arêtes arêtes est soit pancyclique soit égal à ${\displaystyle K_{n/2,n/2}}$^[1].

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

Puissances de graphes

Pour tout graphe ${\displaystyle G}$, la ${\displaystyle k}$-ième puissance ${\displaystyle 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 ${\displaystyle G}$ est au plus ${\displaystyle k}$. Si ${\displaystyle G}$ est sommet-connexe, alors d'après le théorème de Fleischner son carré ${\displaystyle G^{2}}$ est hamiltonien ; on peut montrer qu'il est nécessairement sommet-pancyclique^[14]. Plus généralement, si ${\displaystyle G^{2}}$ est hamiltonien, il est également pancyclique^[15].

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^[16]. Il est également NP-complet de tester si le carré d'un graphe est hamiltonien, et donc s'il est pancyclique^[17].

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^[18].

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).

1. Bondy 1971.
2. Randerath et al. 2002.
3. Schmeichel et Mitchem 1982.
4. Li, Corneil et Mendelsohn 2000, Proposition 2.5..
5. Helden 2007, Corollary 3.78.
6. Bernhart et Kainen 1979.
7. Hakimi et Schmeichel 1979.
8. Skowrońska 1985.
9. Harary et Moser 1966, Corollary 5b.
10. Harary et Moser 1966, Theorem 7.
11. Moon 1966, Theorem 1.
12. Alspach 1967.
13. Häggkvist et Thomassen 1976.
14. Hobbs (1976).
15. Fleischner (1976).
16. Li, Corneil et Mendelsohn 2000, théorèmes 2.3 et 2.4..
17. Underground (1978).
18. Zengxian Tian, Pancyclicity in hamiltonian graph theory (Thèse de doctorat), Université Paris-Saclay, 2021 (HAL tel-03419854).

Bibliographie

• Brian Alspach, « Cycles of each length in regular tournaments », Canadian Mathematical Bulletin, vol. 10, n^o 2,‎ 1967, p. 283–286 (DOI 10.4153/cmb-1967-028-6 , lire en ligne).
• Frank Bernhart et Paul C. Kainen, « The book thickness of a graph », Journal of Combinatorial Theory, Series B, vol. 27, n^o 3,‎ 1979, p. 320–331 (DOI 10.1016/0095-8956(79)90021-2 ).
• John Adrian Bondy, « Pancyclic graphs I », Journal of Combinatorial Theory, Series B, vol. 11, n^o 1,‎ 1971, p. 80–84 (DOI 10.1016/0095-8956(71)90016-5 ).
• Herbert J. Fleischner, « In the square of graphs, Hamiltonicity and pancyclicity, Hamiltonian connectedness and panconnectedness are equivalent concepts », Monatshefte für Mathematik, vol. 82, n^o 2,‎ 1976, p. 125–149 (DOI 10.1007/BF01305995, MR 0427135).
• Roland Häggkvist et Carsten Thomassen, « On pancyclic digraphs », Journal of Combinatorial Theory B, vol. 20, n^o 1,‎ 1976, p. 20–40 (DOI 10.1016/0095-8956(76)90063-0 ).
• Seifollah L. Hakimi et Edward F. Schmeichel, « On the number of cycles of length k in a maximal planar graph », Journal of Graph Theory, vol. 3,‎ 1979, p. 69–86 (DOI 10.1002/jgt.3190030108).
• Frank Harary et Leo Moser, « The theory of round robin tournaments », American Mathematical Monthly, vol. 73, n^o 3,‎ 1966, p. 231–246 (DOI 10.2307/2315334).
• Guido Helden, Hamiltonicity of maximal planar graphs and planar triangulations (Dissertation), Rheinisch-Westfälischen Technischen Hochschule Aachen, 2007 (lire en ligne [archive du 18 juillet 2011]).
• Arthur M. Hobbs, « The square of a block is vertex pancyclic », Journal of Combinatorial Theory Series B, vol. 20, n^o 1,‎ 1976, p. 1–4 (DOI 10.1016/0095-8956(76)90061-7 , MR 0416980).
• Ming-Chu Li, Derek G. Corneil et Eric Mendelsohn, « Pancyclicity and NP-completeness in planar graphs », Discrete Applied Mathematics, vol. 98, n^o 3,‎ 2000, p. 219–225 (DOI 10.1016/S0166-218X(99)00163-8 ).
• Joseph Malkevitch, « On the lengths of cycles in planar graphs », Lecture Notes in Mathematics, Springer-Verlag, vol. 186 « Recent Trends in Graph Theory »,‎ 1971, p. 191–195 (DOI 10.1007/BFb0059437).
• J. W. Moon, « On subtournaments of a tournament », Canadian Mathematical Bulletin, vol. 9, n^o 3,‎ 1966, p. 297–301 (DOI 10.4153/CMB-1966-038-7 , lire en ligne).
• Bert Randerath, Ingo Schiermeyer, Meike Tewes et Lutz Volkmann, « Vertex pancyclic graphs », Discrete Applied Mathematics, vol. 120, n^os 1-3,‎ 2002, p. 219–237 (DOI 10.1016/S0166-218X(01)00292-X ).
• Edward Schmeichel et John Mitchem, « Bipartite graphs with cycles of all even lengths », Journal of Graph Theory, vol. 6, n^o 4,‎ 1982, p. 429–439 (DOI 10.1002/jgt.3190060407).
• Mirosława Skowrońska, « The pancyclicity of Halin graphs and their exterior contractions », dans Brian Alspach et Christopher D. Godsil (éditeurs), Cycles in Graphs, Elsevier Science Publishers B.V., coll. « Annals of Discrete Mathematics » (n^o 27), 1985, p. 179–194.
• Polly Underground, « On graphs with Hamiltonian squares », Discrete Mathematics, vol. 21, n^o 3,‎ 1978, p. 323 (DOI 10.1016/0012-365X(78)90164-4 , MR 522906).

Liens externes

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