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

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

Liens internes

Liens externes

Références

  • Portail des mathématiques
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.