Graphe singleton

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

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 K₁.

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 : ${\displaystyle x}$. Il existe donc ${\displaystyle x}$ façons distinctes de colorer le graphe singleton avec ${\displaystyle x}$ 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 : ${\displaystyle -x}$.

Voir aussi

Liens internes

• Théorie des graphes

Liens externes

• (en) Eric W. Weisstein, Singleton Graph (MathWorld)

Références

1. (en) Eric W. Weisstein, Identity Graph (MathWorld)