Graphe de McGee
Graphe de McGee | |
Représentation du graphe de McGee. | |
Nombre de sommets | 24 |
---|---|
Nombre d'arêtes | 36 |
Distribution des degrés | 3-régulier |
Rayon | 4 |
Diamètre | 4 |
Maille | 7 |
Automorphismes | 32 |
Nombre chromatique | 3 |
Indice chromatique | 3 |
Propriétés | Régulier Cage Hamiltonien |
modifier |
Le graphe de McGee est, en théorie des graphes, un graphe 3-régulier possédant 24 sommets et 36 arêtes.
Propriétés[modifier | modifier le code]
Propriétés générales[modifier | modifier le code]
Le diamètre du graphe de McGee, l'excentricité maximale de ses sommets, est 4, son rayon, l'excentricité minimale de ses sommets, est 4 et sa maille, la longueur de son plus court cycle, est 7. Il s'agit d'un graphe 3-sommet-connexe et d'un graphe 3-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de 3 sommets ou de 3 arêtes.
Le graphe de McGee n'est pas planaire. En fait pour le dessiner sur un plan il faut nécessairement que plusieurs arêtes se croisent. Il est possible de le dessiner avec seulement 8 croisements et ce nombre est minimal[1]. Avec ses 24 sommets, il est le plus petit graphe cubique nécessitant 8 croisements pour être dessiné sur le plan[2].
Coloration[modifier | modifier le code]
Le nombre chromatique du graphe de McGee est 3. C'est-à-dire qu'il est possible de le colorer avec 3 couleurs de telle façon que deux sommets reliés par une arête soient toujours de couleurs différentes mais ce nombre est minimal. Il n'existe pas de 2-coloration valide du graphe.
L'indice chromatique du graphe de McGee est 3. Il existe donc une 3-coloration des arêtes du graphe telle que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes. Ce nombre est minimal.
Propriétés algébriques[modifier | modifier le code]
Le groupe d'automorphismes du graphe de McGee est un groupe d'ordre 32. Il n'agit pas transitivement sur l'ensemble des sommets du graphe mais forme deux orbites, l'une de longueur 8 et l'autre de longueur 16. Le graphe de graphe de McGee est la plus petite cage cubique à ne pas être un graphe sommet-transitif[3].
Le polynôme caractéristique de la matrice d'adjacence du graphe de McGee est : .
Références[modifier | modifier le code]
- (en) Weisstein, Eric W. "Graph Crossing Number" From MathWorld--A Wolfram Web Resource.
- (en) Pegg, E. T. and Exoo, G. "Crossing Number Graphs." Mathematica J. 11, 2009.
- Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, p. 237, 1976.
Voir aussi[modifier | modifier le code]
Liens internes[modifier | modifier le code]
Liens externes[modifier | modifier le code]
- (en) Eric W. Weisstein, McGee Graph (MathWorld)