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 et a reçu son nom en 1969 par Mark Watkins.

Définition et notation 
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  avec deux sommets, deux boucles et une autre arête.

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

Propriétés 

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. 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. Quand n est congru à 3 modulo 6, G(n,2) a exactement trois cycles hamiltoniens . 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.

 Tout graphe de Petersen généralisé est un graphe distance-unité.

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

Mailles 
La maille de G(n,k ) est égale au moins à 3 et au plus à 8, en particulier :

 

Voici un tableau avec les valeurs exactes des mailles :

{| class=wikitable style="text-align: center"
! Condition || Maille
|-
|  || 3
|-
| 
| rowspan=2 | 4
|-
| 
|-
| 
| rowspan=3 | 5
|-
| 
|-
| 
|-
| 
| rowspan=3 | 6
|-
| 
|-
| 
|-
| 
| rowspan=6 | 7
|-
| 
|-
| 
|-
| 
|-
| 
|-
| 
|-
| sinon || 8
|}

Nombre chromatique et index chromatique 
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.

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
.Le graphe de Petersen lui-même est le seul graphe de Petersen généralisé qui n'est pas 3-arêtes coloriable.

Notes et références 

 

Petersen