Graphe de Petersen généralisé

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

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 k² ≡ ±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 ${\displaystyle G(4,1)}$, le graphe de Petersen ${\displaystyle G(5,2)}$, le graphe de Möbius-Kantor ${\displaystyle G(8,3)}$, le graphe dodécaédrique ${\displaystyle G(10,2)}$, le graphe de Desargues ${\displaystyle G(10,3)}$ et le graphe de Nauru ${\displaystyle G(24,5)}$.

• 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 ² ≡ 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].

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

${\displaystyle g(G(n,k))\leq \min \left\{8,k+3,{\frac {n}{\gcd(n,k)}}\right\}.}$

Voici un tableau avec les valeurs exactes des mailles :

Condition	Maille
${\displaystyle n=3k}$	3
${\displaystyle n=4k}$	4
${\displaystyle k=1}$
${\displaystyle n=5k}$	5
${\displaystyle n=5k/2}$
${\displaystyle k=2}$
${\displaystyle n=6k}$	6
${\displaystyle k=3}$
${\displaystyle n=2k+2}$
${\displaystyle n=7k}$	7
${\displaystyle n=7k/2}$
${\displaystyle n=7k/3}$
${\displaystyle k=4}$
${\displaystyle n=2k+3}$
${\displaystyle n=3k\pm 2}$
sinon	8

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 :

${\displaystyle \chi (G(n,k))={\begin{cases}2&{\text{si}}\ n\ {\text{est pair et}}\ k\ {\text{est impair}}\\3&{\text{si}}\ n\ {\text{est impair et}}\ k\ {\text{est pair}}\\\end{cases}}}$

Par exemple, le nombre chromatique de ${\displaystyle G(5,2)}$ est 3.

• 
  Une 3-coloration du graphe de Petersen ${\displaystyle G(5,2)}$
• 
  Une 2-coloration du graphe de Desargues ${\displaystyle G(10,3)}$
• 
  Une 3-coloration du graphe de Dürer ${\displaystyle G(6,2)}$

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 ${\displaystyle G(5,2)}$
• 
  Une 3-coloration des arêtes du graphe de Dürer ${\displaystyle G(6,2)}$
• 
  Une 3-coloration des arêtes du dodécaèdre ${\displaystyle G(10,2)}$
• 
  Une 3-coloration des arêtes du graphe de Desargues ${\displaystyle G(10,3)}$
• 
  Une 3-colorationdes arêtes du graphe de Nauru ${\displaystyle G(12,5)}$

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

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

• Portail des mathématiques
• Portail de l'informatique théorique