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.
Propriétés
Propriétés générales Le 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 Du 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 Le 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 Eric W. Weisstein, Identity Graph (MathWorld).
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
Liens internes Théorie des graphes
Liens externes Eric W. Weisstein, Singleton Graph (MathWorld)
Références
Singleton