Graphe singleton

Graphe singleton
Graphe singleton
Complete graph K1.svg
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 Consultez la documentation du modèle

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.

Sommaire

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.

Coloriage

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

Propriétés algébriques

Le groupe d'automorphismes du graphe singleton ne contienne 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 du graphe singleton est : − x.

Voir aussi

Liens internes

Liens externes

Références


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Graphe singleton de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Graphe complet — K5 Notation Kn Nombre de sommets n Nombre d arêtes …   Wikipédia en Français

  • Graphe intégral — En théorie des graphes, un graphe intégral est un graphe dont le spectre de la matrice d adjacence ne contient que des entiers[1]. En d autres termes, les racines de son polynôme caractéristiques sont toutes entières. Leur étude fut introduite… …   Wikipédia en Français

  • Graphe asymétrique — En théorie des graphes, un graphe asymétrique ou graphe identité est un graphe dont le groupe d automorphismes du est d ordre 1. C est donc un graphe n admettant aucun automorphisme autre que l identité. Le plus petit graphe asymétrique est le… …   Wikipédia en Français

  • Graphe de Hoffman-Singleton — Schéma du graphe de Hoffman Singleton, présentant ses 50 sommets sous la forme de deux cercles concentriques de 25 sommets. Nombre de sommets 50 Nombre d arêtes 175 Distribution des degrés …   Wikipédia en Français

  • Graphe D'Hoffman-Singleton — Schéma du graphe d Hoffman Singleton, présentant ses 50 sommets sous la forme de deux cercles concentriques de 25 sommets. Nombre de sommets 50 Nombre d arêtes 175 Distribution des degrés 7 régulier Diamètre 2 …   Wikipédia en Français

  • Graphe d'Hoffman-Singleton — Schéma du graphe d Hoffman Singleton, présentant ses 50 sommets sous la forme de deux cercles concentriques de 25 sommets. Nombre de sommets 50 Nombre d arêtes 175 Distribution des degrés 7 régulier Diamètre 2 …   Wikipédia en Français

  • Graphe d'hoffman-singleton — Schéma du graphe d Hoffman Singleton, présentant ses 50 sommets sous la forme de deux cercles concentriques de 25 sommets. Nombre de sommets 50 Nombre d arêtes 175 Distribution des degrés 7 régulier Diamètre 2 …   Wikipédia en Français

  • Graphe de Moore — En théorie des graphes, un graphe de Moore est un graphe régulier dont le nombre de sommets, pour un degré et un diamètre donnés, est maximal. Les graphes de Moore ont été nommés par Alan Hoffman et Robert Singleton en 1960 en hommage à Edward F …   Wikipédia en Français

  • Graphe distance-régulier — En théorie des graphes, un graphe est distance régulier si pour tous sommets , le nombre de sommets voisins de u à distance i et le nombre de sommets voisins de v à distance j ne dépendent que de i,j et de la distance d(u,v) entre u et v.… …   Wikipédia en Français

  • Graphe fortement régulier — Le graphe de Paley d ordre 13, un graphe fortement régulier de type (13,6,2,3). En théorie des graphes, qui est un domaine des mathématiques, un graphe fortement régulier est un type de graphe qui est en particulier un graphe régulier. Soit G =… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”