Graphe singleton

graphe possédant un unique sommet et aucune arête

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
Image illustrative de l’article 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

Propriétés

modifier

Propriétés générales

modifier

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

modifier

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

modifier

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[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

modifier

Liens internes

modifier

Liens externes

modifier

Références

modifier