Utilisateur:Koko90/GG
| $NAME$ | |
| Nombre de sommets | $NB_SOMMET$ |
|---|---|
| Nombre d'arêtes | $NB_ARETE$ |
| Distribution des degrés | $DEG_SOM$-régulier |
| Rayon | $RAYON$ |
| Diamètre | $DIAMETRE$ |
| Maille | $MAILLE$ |
| Automorphismes | $AUT$ |
| Nombre chromatique | $NB_COL$ |
| Indice chromatique | $INDX_COL$ |
modifier  |
|
Le $NAME$ est, en théorie des graphes, un graphe $DEG_SOM$-régulier possédant $NB_SOMMET$ sommets et $NB_ARETE$ arêtes.
Propriétés
[modifier | modifier le code]Propriétés générales
[modifier | modifier le code]Le diamètre du $NAME$, l'excentricité maximale de ses sommets, est $DIAMETRE$, son rayon, l'excentricité minimale de ses sommets, est $RAYON$ et sa maille, la longueur de son plus court cycle, est $MAILLE$. Il s'agit d'un graphe $CONNEXE_SOMMET$-sommet-connexe et d'un graphe $CONNEXE_ARETE$-arête-connexe, c'est-à-dire qu'il est connexe et que pour le rendre déconnecté il faut le priver au minimum de $CONNEXE_SOMMET$ sommets ou de $CONNEXE_ARETE$ arêtes.
Coloriage
[modifier | modifier le code]<SI $NB_COL$>
Le nombre chromatique du $NAME$ est $NB_COL$. C'est-à-dire qu'il est possible de le colorer avec $NB_COL$ couleurs de tel façon que deux sommets reliés par une arêtes soient toujours de couleurs différentes mais ce nombre est minimal. Il n'existe pas de $NB_COL-1$ coloration valide du graphe.
<SI $INDX_COL$>
L'indice chromatique du $NAME$ est $INDX_COL$. Il existe donc une $INDX_COL$-coloration des arêtes du graphe tels que deux arêtes incidentes à un même sommets soient toujours de couleurs différentes. Ce nombre est minimal.
<SI $POLY_CHROMATIQUE$>
Il est possible de compter les colorations distinctes d'un graphe. Cela donne une fonction dépendant du nombre de couleurs autorisé. Cette fonction est polynomiale et est qualifiée de polynôme chromatique du graphe. Ce polynôme admet pour racines tous les entiers positifs ou nuls strictement inférieurs à $NB_COL$ et est de degrés $NB_SOMMET$. Il est égal à : .
Propriétés algébriques
[modifier | modifier le code]Le groupe d'automorphismes du $NAME$ est un groupe d'ordre $AUT$.
<SI graphe seulement Arête-transitifs>
Il agit transitivement sur l'ensemble des arêtes du $NAME$, faisant de lui un graphe arête-transitif, c'est-à-dire un graphe dont toutes les arêtes jouent exactement le même rôle.
<SI graphe seulement Sommet-transitifs>
Il agit transitivement sur l'ensemble des sommets du $NAME$, faisant de lui un graphe sommets-transitif, c'est-à-dire un graphe dont toutes les sommets jouent exactement le même rôle.
<SI graphe Arc-transitifs>
Il agit transitivement sur l'ensemble des sommets, des arêtes et des arcs de NAME$, faisant de lui un graphe graphe symétrique.
<SI FOSTER> Le $NAME$ est symétrique, c'est-à-dire que son groupe d'automorphismes agit transitivement sur ses arêtes, ses sommets et ses arcs. Il est donc également arête-transitif et sommet-transitif. Le $NAME$ est l'unique graphe cubique symétrique à $NB_SOMMET$ sommets et sa notation dans le Foster Census, le catalogue classifiant tout les graphes cubiques symétriques, est F$NB_SOMMET$A.[1][2]
Le polynôme caractéristique du $NAME$ est : .
Voir aussi
[modifier | modifier le code]Liens internes
[modifier | modifier le code]Liens externes
[modifier | modifier le code]- (en) Eric W. Weisstein, [$MATHWOLRD_URL$ $MATHWOLRD_NAME$] (MathWorld)
Références
[modifier | modifier le code]- (en) Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002
- (en) Royle, G. "Cubic Symmetric Graphs (The Foster Census)."
