Graphe singleton
Le graphe singleton est, en théorie des graphes, le graphe possédant un unique sommet et aucune arête. C'est le graphe complet K1.
| Graphe singleton | |
 Représentation du graphe singleton. | |
| Nombre de sommets | 1 |
|---|---|
| Nombre d'arêtes | 0 |
| Distribution des degrés | 0-régulier |
| Rayon | 0 |
| Diamètre | 0 |
| Maille | ∞ |
| Automorphismes | 1 ({id}) |
| Nombre chromatique | 1 |
| Indice chromatique | 1 |
| Propriétés | Arête-transitif Biparti Complet Distance-régulier Fortement régulier Hamiltonien Parfait Planaire Régulier Sommet-transitif Asymétrique |
modifier  |
|
Propriétés
modifierPropriétés générales
modifierLe diamètre du graphe singleton, l'excentricité maximale de ses sommets, est 0, son rayon, l'excentricité minimale de ses sommets, est 0 et comme il ne possède aucun cycle, sa maille est infinie. Par convention, il est cependant considéré comme étant un graphe hamiltonien.
Le graphe singleton est également biparti, planaire et graphe régulier.
Coloration
modifierDu fait de sa structure réduite à un sommet, le nombre chromatique et l'indice chromatique du graphe singleton sont égaux à 1.
Le polynôme chromatique du graphe singleton est : . Il existe donc façons distinctes de colorer le graphe singleton avec couleurs.
Propriétés algébriques
modifierLe groupe d'automorphismes du graphe singleton ne contient que l'élément neutre. Il est donc d'ordre 1. Cela fait du graphe singleton le plus petit graphe asymétrique. Si on exclut ce cas trivial, un graphe asymétrique doit avoir au moins 6 sommets[1].
De par sa structure triviale, le graphe singleton 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 polynôme caractéristique de la matrice d'adjacence du graphe singleton est : .
Voir aussi
modifierLiens internes
modifierLiens externes
modifierRéférences
modifier- (en) Eric W. Weisstein, Identity Graph (MathWorld)
