Voir la source de Graphe pancyclique

[[Fichier:Pancyclic_octahedron.svg|vignette| 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 (mathématiques discrètes)|graphe]] qui contient des [[Cycle (théorie des graphes)|cycles]] de toutes les longueurs de trois jusqu'au nombre de [[Sommet (théorie des graphes)|sommets]] du graphe. Les graphes pancycliques sont une généralisation des [[Chaîne hamiltonienne|graphes hamiltoniens]] qui ont un cycle qui passe par tous les sommets.

== Définitions ==
Un graphe <math>G</math> à <math>n</math>  sommets est '''pancyclique''' si, pour tout entier <math>k</math> avec <math>3 \leq k \leq n</math>, le graphe contient un cycle de longueur <math>k</math><ref name="b71">{{harvsp|Bondy|1971}}.</ref>. Il est '''nœud-pancyclique''' ou '''sommet-pancyclique''' si, pour chaque sommet <math>s</math> et tout <math>k</math> avec <math>3 \leq k \leq n</math>, il contient un cycle de longueur <math>k</math> qui passe par <math>s</math><ref name="rstv02">{{harvsp|Randerath|Schiermeyer|Tewes|Volkmann|2002}}.</ref>. De même, il est '''arête-pancyclique''' si, pour chaque arête <math>a</math> et tout <math>k</math>, il contient un cycle de longueur <math>k</math> qui utilise <math>a</math><ref name="rstv02" />.

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''<ref>{{harvsp|Schmeichel|Mitchem|1982}}.</ref>.

Le nombre de graphes pancycliques à <math>n=0,1,\ldots</math> sommets est 0, 0, 1, 2, 7, 43, 372, 6132, 176797, 9302828, ... ({{OEIS|A286684}}).

== Graphes planaires ==
Un [[graphe planaire extérieur]] maximal est par définition un graphe formé par un [[polygone simple]] du plan en [[Triangulation d'un polygone|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<ref>{{harvsp|Li|Corneil|Mendelsohn|2000|loc=Proposition 2.5.}}.</ref>. Il en est de même pour les graphes qui ont un sous-[[Lexique de la théorie des graphes|graphe couvrant]] planaire extérieur maximal, comme c'est le cas par exemple pour les [[Graphe roue|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<ref>{{harvsp|Helden|2007|loc=Corollary 3.78}}.</ref> 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 [[Graphe planaire extérieur|planaires extérieurs]] maximaux  s'applique<ref>{{harvsp|Bernhart|Kainen|1979}}.</ref>. 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<ref>{{harvsp|Hakimi|Schmeichel|1979}}.</ref>.
[[Fichier:Halin_no_8-cycle.svg|vignette| Un [[graphe de Halin]] presque pancyclique, avec des cycles de toutes longueurs jusqu'à ''n'' sauf de longueur 8.]]

Les [[Graphe de Halin|graphes de Halin]] sont les graphes planaires formés à partir d'une représentation planaire d'un [[arbre (théorie des graphes)|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<ref>{{harvsp|Skowrońska|1985}}.</ref>.

{{harvsp|Bondy|1971|texte = 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 [[Conjecture|conjecturé]] que tout graphe planaire à 4-connexe est pancyclique. {{harvsp|Malkevitch|1971|texte =  Malkevitch (1971)}} a trouvé une famille de contre-exemples.

== Tournois ==
Un [[tournoi (théorie des graphes)|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 [[Composante fortement connexe|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''<ref>{{harvsp|Harary|Moser|1966|loc=Corollary 5b}}.</ref>. Un tournoi fort est pancyclique<ref>{{harvsp|Harary|Moser|1966|loc=Theorem 7}}.</ref>   et nœud-pancyclique<ref>{{harvsp|Moon|1966|loc=Theorem 1}}.</ref>. Si un tournoi est [[Graphe régulier|régulier]] (chaque concurrent a le même nombre de victoires et de défaites que chaque autre concurrent), alors il est également pancyclique<ref>{{harvsp|Alspach|1967}}.</ref> ;  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é à <math>n</math> sommets avec au moins <math>n^2/4</math> arêtes, et sans arêtes multiples ou boucles, contient soit un triangle, soit le [[graphe biparti complet]] <math>K_{n/2,n/2}</math>. Ce théorème peut être précisé : tout graphe hamiltonien non orienté avec au moins <math>n^2/4</math> arêtes arêtes est soit pancyclique soit égal à <math>K_{n/2,n/2}</math><ref name="b71"/>.

Il existe des [[Graphe orienté|graphes orientés]] hamiltoniens à <math>n</math> sommets avec <math>n(n+1)/2-3</math>  arcs qui ne sont pas pancycliques, mais un graphe orienté hamiltonien avec au moins <math>n(n+1)/2-1</math> arcs est pancyclique. De plus, tout graphe orienté à <math>n</math> sommets fortement connexe dans lequel chaque sommet est de degré au moins <math>n</math> (en comptant les arêtes entrantes et les sortantes) est soit pancyclique, soit un graphe orienté bipartite complet<ref>{{harvsp|Häggkvist|Thomassen|1976}}.</ref>.

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

== Complexité algorithmique ==
Il est [[Problème NP-complet|NP-complet]] de tester si un graphe est pancyclique, même dans le cas particulier des [[Graphe cubique|graphes cubiques]] [[Graphe sommet-connexe|3-connexes]], et il est aussi NP-complet de tester si un graphe est sommet-pancyclique, même dans le cas particulier des [[Graphe polyédrique|graphes polyédriques]]<ref>{{harvsp|Li|Corneil|Mendelsohn|2000|loc=théorèmes 2.3 et 2.4.}}.</ref>. Il est également NP-complet de tester si le carré d'un graphe est hamiltonien, et donc s'il est pancyclique{{Sfnp|Underground|1978}}.

<!-- == Familles de graphes pancycliques ==
1. {{Lien|trad=Antiprism graph|fr=graphe antiprisme|texte = graphes antiprismes}},

2. Chang graphs Chang graphs,

3. dipyramidal graphs,

4. Johnson graphs,

5. Mathon graphs,

6. Paulus graphs,

7. Sierpiński gasket graphs,

8. sun graphs,

9. tetrahedral graphs, and

10. wheel graphs. 

 -->== Historique ==
Les graphes pancycliques ont été étudiés pour la première fois dans le contexte des tournois par {{harvsp|Harary|Moser|1956|texte = Harary et Moser (1966)}}, {{harvsp|Moon|1966|texte=Moon (1966)}} et {{harvsp|Alspach|1967|texte=Alspach (1967))}}. Le concept de pancyclicité a été nommé et étendu aux graphes non orientés par {{harvsp||Bondy|1971texte=Bondy (1971)}}. Un travail plus récent est la thèse de Zengxian Tian<ref>{{Ouvrage
|nature ouvrage = Thèse de doctorat
|auteur1= Zengxian Tian
|titre= Pancyclicity in hamiltonian graph theory
|éditeur= Université Paris-Saclay
|année= 2021
|isbn=
|hal = tel-03419854
}}.</ref>.

== Notes et références ==
{{Traduction/référence|en|Pancyclic graph|1037800091}}
{{Références}}

== Bibliographie ==
{{refbegin|colwidth=30em}}
*{{article
 | nom = Alspach | prénom = Brian | lien auteur = Brian Alspach
 | numéro = 2
 | journal = [[Canadian Mathematical Bulletin]]
 | pages = 283–286
 | titre = Cycles of each length in regular tournaments
 | url = http://cms.math.ca/cmb/v10/p283
 | volume = 10
 | année = 1967
 | doi=10.4153/cmb-1967-028-6 | accès doi = libre}}.
*{{article
 | nom1 = Bernhart | prénom1 = Frank
 | nom2 = Kainen | prénom2 = Paul C. | lien auteur2 = Paul Chester Kainen
 | doi = 10.1016/0095-8956(79)90021-2
 | numéro = 3
 | journal = [[Journal of Combinatorial Theory]], Series B
 | pages = 320–331
 | titre = The book thickness of a graph
 | volume = 27
 | année = 1979| accès doi = libre
 }}.
*{{article
 | nom = Bondy | prénom = John Adrian | lien auteur = John Adrian Bondy
 | doi = 10.1016/0095-8956(71)90016-5
 | numéro = 1
 | journal = [[Journal of Combinatorial Theory]], Series B
 | pages = 80–84
 | titre = Pancyclic graphs I
 | volume = 11
 | année = 1971| accès doi = libre
 }}.
*{{article
 | nom = Fleischner | prénom = Herbert J.
 | doi = 10.1007/BF01305995
 | numéro = 2
 | journal = Monatshefte für Mathematik
 | mr = 0427135
 | pages = 125–149
 | titre = In the square of graphs, Hamiltonicity and pancyclicity, Hamiltonian connectedness and panconnectedness are equivalent concepts
 | volume = 82
 | année = 1976}}.
*{{article
 | nom1 = Häggkvist | prénom1 = Roland
 | nom2 = Thomassen | prénom2 = Carsten | lien auteur2 = Carsten Thomassen
 | doi = 10.1016/0095-8956(76)90063-0
 | numéro = 1
 | journal = [[Journal of Combinatorial Theory]] B
 | pages = 20–40
 | titre = On pancyclic digraphs
 | volume = 20
 | année = 1976| accès doi = libre
 }}.
*{{article
 | nom1 = Hakimi | prénom1 = Seifollah L.
 | nom2 = Schmeichel | prénom2 =  Edward F.
 | doi = 10.1002/jgt.3190030108
 | journal = Journal of Graph Theory
 | pages = 69–86
 | titre = On the number of cycles of length ''k'' in a maximal planar graph
 | volume = 3
 | année = 1979}}.
*{{article
 | nom1 = Harary | prénom1 = Frank | lien auteur1 = Frank Harary
 | nom2 = Moser | prénom2 = Leo | lien auteur2 = Leo Moser
 | doi = 10.2307/2315334
 | numéro = 3
 | journal = [[American Mathematical Monthly]]
 | pages = 231–246
 | titre = The theory of round robin tournaments
 | volume = 73
 | année = 1966}}.
*{{ouvrage
 |nom        = Helden
 |prénom       = Guido
 |éditeur   = Rheinisch-Westfälischen Technischen Hochschule Aachen
 |titre       = Hamiltonicity of maximal planar graphs and planar triangulations
 |url         = http://darwin.bth.rwth-aachen.de/opus3/volltexte/2007/1949/pdf/Helden_Guido.pdf
 |nature ouvrage     = Dissertation
 |année        = 2007
 |archiveurl  = https://web.archive.org/web/20110718172008/http://darwin.bth.rwth-aachen.de/opus3/volltexte/2007/1949/pdf/Helden_Guido.pdf
 |archivedate = 2011-07-18
}}.
*{{article
 | nom = Hobbs | prénom = Arthur M. | lien auteur = Arthur Hobbs (mathematician)
 | doi = 10.1016/0095-8956(76)90061-7
 | numéro = 1
 | journal = [[Journal of Combinatorial Theory]] Series B
 | mr = 0416980
 | pages = 1–4 
 | titre = The square of a block is vertex pancyclic
 | volume = 20
 | année = 1976| accès doi = libre
 }}.
*{{article
 | nom1 = Li | prénom1 = Ming-Chu
 | nom2 = Corneil | prénom2 = Derek G. | lien auteur2 = Derek Corneil
 | nom3 = Mendelsohn | prénom3 = Eric
 | doi = 10.1016/S0166-218X(99)00163-8
 | numéro = 3
 | journal = Discrete Applied Mathematics
 | pages = 219–225
 | titre = Pancyclicity and NP-completeness in planar graphs
 | volume = 98
 | année = 2000| accès doi = libre
 }}.
*{{article
 | nom = Malkevitch | prénom = Joseph
 | titre = On the lengths of cycles in planar graphs
 | doi = 10.1007/BFb0059437
 | passage = 191–195
 | éditeur = Springer-Verlag
 | journal = Lecture Notes in Mathematics
 | titre volume = Recent Trends in Graph Theory
 | volume = 186
 | année = 1971}}.
*{{article
 | nom = Moon | prénom = J. W.
 | numéro = 3
 | journal = [[Canadian Mathematical Bulletin]]
 | pages = 297–301
 | titre = On subtournaments of a tournament
 | url = http://cms.math.ca/cmb/v9/p297 | doi = 10.4153/CMB-1966-038-7 | accès doi = libre
 | volume = 9
 | année = 1966}}.
*{{article
 | nom1 = Randerath | prénom1 = Bert
 | nom2 = Schiermeyer | prénom2 = Ingo
 | nom3 = Tewes | prénom3 = Meike
 | nom4 = Volkmann | prénom4 = Lutz
 | doi = 10.1016/S0166-218X(01)00292-X
 | numéro = 1-3
 | journal = Discrete Applied Mathematics
 | pages = 219–237
 | titre = Vertex pancyclic graphs
 | volume = 120
 | année = 2002| accès doi = libre
 }}.
*{{article
 | nom1 = Schmeichel | prénom1 = Edward
 | nom2 = Mitchem | prénom2 = John
 | doi = 10.1002/jgt.3190060407
 | numéro = 4
 | journal = Journal of Graph Theory
 | pages = 429–439
 | titre = Bipartite graphs with cycles of all even lengths
 | volume = 6
 | année = 1982}}.
*{{chapitre
 | nom = Skowrońska | prénom = Mirosława
 | titre = The pancyclicity of Halin graphs and their exterior contractions
 | auteurs ouvrage =Brian Alspach et Christopher D. Godsil (éditeurs)
 | passage = 179–194
 | éditeur = Elsevier Science Publishers B.V.
 | collection = Annals of Discrete Mathematics
 | titre ouvrage = Cycles in Graphs
 | numéro dans collection = 27
 | année = 1985}}.
*{{article
 | nom = Underground | prénom = Polly | lien auteur = Václav Chvátal
 | doi = 10.1016/0012-365X(78)90164-4
 | numéro = 3
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 522906
 | page = 323
 | titre = On graphs with Hamiltonian squares
 | volume = 21
 | année = 1978| accès doi = libre
 }}.
{{refend}}

== Liens externes ==
* {{MathWorld|nom_url=PancyclicGraph|titre=Pancyclic Graph}}
{{portail|mathématiques|informatique théorique}}

[[Catégorie:Famille de graphes]]