Voir la source de 46-graphe de Grinberg


{{Infobox Graphe
 | nom                = 46-graphe de Grinberg
 | image              = 
 | légende            = 
 | distribution       = 3-[[Graphe régulier|régulier]]
 | sommets            = 46
 | arêtes             = 69
 | automorphismes     = 6 ([[groupe symétrique|S]]<sub>3</sub>)
 | maille             = 5
 | diamètre           = 8
 | rayon              = 6
 | nombre chromatique = 3
 | indice chromatique = 3
 | propriétés         = [[Graphe cubique|Cubique]]<br>[[Graphe planaire|Planaire]]<br>[[Graphe sans triangle|Sans triangle]]
}}
Le '''46-graphe de Grinberg''' est, en [[théorie des graphes]], un [[graphe régulier|graphe 3-régulier]] possédant 46 sommets et 69 arêtes.

== Propriétés ==

=== Propriétés générales ===
Le [[Diamètre (théorie des graphes)|diamètre]] du 46-graphe de Grinberg, l'excentricité maximale de ses sommets, est 8, son [[Rayon (théorie des graphes)|rayon]], l'excentricité minimale de ses sommets, est 6 et sa [[Maille (théorie des graphes)|maille]], la longueur de son plus court [[cycle (graphe)|cycle]], est 5. Il s'agit d'un graphe 3-[[Graphe sommet-connexe|sommet-connexe]] et d'un graphe 3-[[Graphe arête-connexe|arête-connexe]], c'est-à-dire qu'il est [[graphe connexe|connexe]] et que pour le rendre déconnecté il faut le priver au minimum de 3 sommets ou de 3 arêtes.

=== Coloration ===
Le [[nombre chromatique]] du 46-graphe de Grinberg 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 46-graphe de Grinberg est 3. Il existe donc une 3-coloration des arêtes du graphe telles que deux arêtes incidentes à un même sommet soient toujours de couleurs différentes. Ce nombre est minimal.

=== Propriétés algébriques ===
Le groupe d'[[automorphisme]]s du 46-graphe de Grinberg est un groupe d'ordre 6 isomorphe au [[groupe symétrique]] S<sub>3</sub>.

Le [[polynôme caractéristique]] de la [[matrice d'adjacence]] du 46-graphe de Grinberg est : <math>(x-3) (x-1) (x+2)^2 (x^2-x-1) (x^2+x-1) (x^2+2 x-1)^3 (x^6-2 x^5-8 x^4+14 x^3+16 x^2-22 x-5) (x^{13}-2 x^{12}-17 x^{11}+34 x^{10}+103 x^9-217 x^8-246 x^7+621 x^6+100 x^5-693 x^4+281 x^3+68 x^2-38 x+2)^2</math>

== Voir aussi ==

=== Liens internes ===
* [[Théorie des graphes]]

=== Liens externes ===
* {{en}} [[Eric W. Weisstein]], [http://mathworld.wolfram.com/GrinbergGraphs.html Grinberg Graphs] ([[MathWorld]])

=== Références ===
<references />

{{Portail|Mathématiques}}

[[Catégorie:Graphe remarquable|Grinberg, 46-graphe]]