Graphe de Petersen généralisé
En théorie des graphes, les graphes de Petersen généralisés sont une famille de graphes cubiques formés en connectant les sommets d'un polygone régulier aux sommets correspondants d'un polygone régulier étoilé. Ils comprennent le graphe de Petersen et généralisent l'une des manières de construire le graphe de Petersen. La famille des graphes de Petersen généralisés a été introduite en 1950 par H. S. M. Coxeter[1] et a reçu son nom en 1969 par Mark Watkins[2].
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/51/D%C3%BCrer_graph.svg/220px-D%C3%BCrer_graph.svg.png)
Définition et notation
modifierDans la notation introduite par Watkins, G(n,k) est un graphe avec un ensemble de 2n sommets
et ensemble d'arêtes
où les indices sont modulo n et k < n /2. Certains auteurs utilisent la notation GPG(n,k). La notation de Coxeter pour le même graphe est {n} + {n/k} ; c'est une combinaison des symboles de Schläfli pour le polygone régulier et pour le polygone régulier étoilé à partir desquels le graphe est formé. Le graphe de Petersen lui-même est le graphe G(5,2), resp. {5} + {5/2}.
Tout graphe de Petersen généralisé peut également être construit à partir d'un graphe de tension (en) avec deux sommets, deux boucles et une autre arête.
Exemples
modifierParmi les graphes de Petersen généralisés il y a les graphes prismatiques G(n,1), le graphe de Dürer G(6,2), le graphe de Möbius-Kantor G(8, 3), le dodécaèdre G(10,2), le graphe de Desargues G(10,3) et le graphe de Nauru G(12,5).
Quatre graphes de Petersen généralisés, à savoir le 3-prisme, le 5-prisme, le graphe de Dürer et G(7,2), font partie des sept graphes cubiques, 3-sommet-connexes et « bien couverts » (ce qui signifie que tous leurs ensembles indépendants maximaux ont même taille)[3].
Propriétés
modifier![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Generalized_Petersen_9_2_Hamiltonicity.svg/220px-Generalized_Petersen_9_2_Hamiltonicity.svg.png)
La famille des graphes de Petersen généralisés possède un certain nombre de propriétés remarquables, parmi lesquelles les suivantes :
- G(n,k) est sommet-transitif (ce qui signifie qu'il a des automorphismes qui envoient tout sommet sur tout autre sommet) si et seulement si (n,k) = (10, 2) ou k2 ≡ ±1 (mod n ).
- G(n,k) est arête-transitif (il existe des automorphismes de toute arête sur toute autre arête) dans les seuls sept cas suivants : (n,k) = (4, 1), (5, 2), (8, 3), (10, 2), (10, 3), (12, 5), (24, 5). Ces sept graphes sont donc les seuls graphes de Petersen généralisés symétriques[4]. Donc le graphe de Nauru est un des sept graphes de Petersen généralisés symétriques. Ces sept sont le graphe hexaédrique , le graphe de Petersen , le graphe de Möbius-Kantor , le graphe dodécaédrique , le graphe de Desargues et le graphe de Nauru .
- G(n,k) est biparti si et seulement si n est pair et k est impair.
- G(n,k) est un graphe de Cayley si et seulement si k 2 ≡ 1 (mod n ).
- G(n,k) est hypohamiltonien lorsque n est congru à 5 modulo 6 et k = 2, k =n − 2, ou k = (n ± 1)/2 (ces quatre choix de k conduisent à des graphes isomorphes). Il est également non hamiltonien lorsque n est divisible par 4, au moins égal à 8, et k = n/2. Dans tous les autres cas, il possède un cycle hamiltonien[5]. Quand n est congru à 3 modulo 6, G(n,2) a exactement trois cycles hamiltoniens[6] . Pour G(n,2), le nombre de cycles hamiltoniens peut être calculé par une formule qui dépend de la classe de congruence de n modulo 6 et fait intervenir les nombres de Fibonacci[7].
- Tout graphe de Petersen généralisé est un graphe distance-unité[8].
Isomorphismes
modifierG(n,k) est isomorphe à G(n,l) si et seulement si kl ≡ ±1 (mod n )[9].
Mailles
modifierLa maille de G(n,k ) est égale au moins à 3 et au plus à 8, en particulier[10] :
Voici un tableau avec les valeurs exactes des mailles :
Condition Maille 3 4 5 6 7 sinon 8
Nombre chromatique et index chromatique
modifierEn tant que graphes réguliers, et selon le théorème de Brooks, le nombre chromatique d'un graphe de Petersen généralisé ne peut être supérieur à son degré . Les graphes de Petersen généralisés sont cubiques, leur nombre chromatique est donc 2 ou 3. Plus précisément, on a :
Par exemple, le nombre chromatique de est 3.
-
Une 3-coloration du graphe de Petersen
-
Une 2-coloration du graphe de Desargues
-
Une 3-coloration du graphe de Dürer
Le graphe de Petersen, qui est un snark, a un indice chromatique égal à 4. Tous les autres graphes de Petersen généralisés ont l'indice chromatique égal à 3[11].
Le graphe de Petersen généralisé G(9, 2) est l'un des rares graphes connus pour ne posséder qu'une seule 3-coloration des arêtes[12].
-
Une 4-coloration des arêtes du graphe de Petersen
-
Une 3-coloration des arêtes du graphe de Dürer
-
Une 3-coloration des arêtes du dodécaèdre
-
Une 3-coloration des arêtes du graphe de Desargues
-
Une 3-colorationdes arêtes du graphe de Nauru
Le graphe de Petersen lui-même est le seul graphe de Petersen généralisé qui n'est pas 3-arêtes coloriable[13].
Notes et références
modifier- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Generalized Petersen graph » (voir la liste des auteurs).
- H. S. M. Coxeter, « Self-dual configurations and regular graphs », Bulletin of the American Mathematical Society, vol. 56, no 5, , p. 413–455 (DOI 10.1090/S0002-9904-1950-09407-5
).
- Mark E. Watkins, « A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs », Journal of Combinatorial Theory, vol. 6, no 2, , p. 152–164 (DOI 10.1016/S0021-9800(69)80116-X
).
- S. R. Campbell, Mark N. Ellingham et Gordon F. Royle, « A characterisation of well-covered cubic graphs », Journal of Combinatorial Mathematics and Combinatorial Computing, vol. 13, , p. 193–212 (MR 1220613).
- R. Frucht, J. E. Graver et M. E. Watkins, « The groups of the generalized Petersen graphs », Proceedings of the Cambridge Philosophical Society, vol. 70, no 2, , p. 211–218 (DOI 10.1017/S0305004100049811).
- B. R. Alspach, « The classification of Hamiltonian generalized Petersen graphs », Journal of Combinatorial Theory, Series B, vol. 34, no 3, , p. 293–312 (DOI 10.1016/0095-8956(83)90042-4, MR 0714452).
- Andrew Thomason, « Cubic graphs with three Hamiltonian cycles are not always uniquely edge colorable », Journal of Graph Theory, vol. 6, no 2, , p. 219–221 (DOI 10.1002/jgt.3190060218).
-
Allen J. Schwenk, « Enumeration of Hamiltonian cycles in certain generalized Petersen graphs », Journal of Combinatorial Theory, vol. 47, no 1, , p. 53–59 (DOI 10.1016/0095-8956(89)90064-6
, MR 1007713).
- Arjana Žitnik, Boris Horvat et Tomaž Pisanski, « All generalized Petersen graphs are unit-distance graphs », IMFM preprints, vol. 1109, (lire en ligne).
- Alice Steimle et William Staton, « The isomorphism classes of the generalized Petersen graphs », Discrete Mathematics, vol. 309, no 1, , p. 231–237 (DOI 10.1016/j.disc.2007.12.074
).
- Daniela Ferrero et Sarah Hanusch, « Component connectivity of generalized Petersen graphs », International Journal of Computer Mathematics, vol. 91, no 9, , p. 1940–1963 (ISSN 0020-7160, DOI 10.1080/00207160.2013.878023, lire en ligne [archive du ], consulté le )
- Frank Castagna et Geert Caleb Ernst Prins, « Every generalized Petersen graph has a Tait coloring », Pacific Journal of Mathematics, vol. 40, no 1, , p. 53–58 (ISSN 0030-8730, DOI 10.2140/pjm.1972.40.53
, MR 304223, zbMATH 0236.05106)
- Béla Bollobás, Extremal Graph Theory, Dover, , p. 233. Réimpression de l'édition d'Academic Press de 1978.
- Frank Castagna et Geert Prins, « Every Generalized Petersen Graph has a Tait Coloring », Pacific Journal of Mathematics, vol. 40, , p. 53–58 (DOI 10.2140/pjm.1972.40.53
).