Aller au contenu

Graphe de Petersen généralisé

Un article de Wikipédia, l'encyclopédie libre.
Le graphe de Dürer G (6, 2).

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

Définition et notation

[modifier | modifier le code]

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

Parmi 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 | modifier le code]
L'un des trois cycles hamiltoniens de G(9,2). Les deux autres cycles hamiltoniens du même graphe sont symétriques dans des rotations de 40° du dessin.

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

Isomorphismes

[modifier | modifier le code]

G(n,k) est isomorphe à G(n,l) si et seulement si kl ≡ ±1 (mod n )[9].

La 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

[modifier | modifier le code]

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

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

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 | modifier le code]
  1. 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 Accès libre).
  2. 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 Accès libre).
  3. 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).
  4. 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).
  5. 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).
  6. 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).
  7. 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 Accès libre, MR 1007713).
  8. Arjana Žitnik, Boris Horvat et Tomaž Pisanski, « All generalized Petersen graphs are unit-distance graphs », IMFM preprints, vol. 1109,‎ (lire en ligne).
  9. 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 Accès libre).
  10. 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 )
  11. 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 Accès libre, MR 304223, zbMATH 0236.05106)
  12. Béla Bollobás, Extremal Graph Theory, Dover, , p. 233. Réimpression de l'édition d'Academic Press de 1978.
  13. 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 Accès libre).