Graphe fortement régulier

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 = (V,E) un graphe régulier ayant v sommets et degré k. On dit que G est fortement régulier s'il existe deux entiers λ et μ tels que

  • Toute paire de sommets adjacents a exactement λ voisins communs.
  • Toute paire de sommets non-adjacents a exactement μ voisins communs.

Une graphe avec ces propriétés est appelé un graphe fortement régulier de type (v,k,λ,μ).

Lorsque μ n'est pas nul, un tel graphe est en particulier un graphe distance-régulier.

Propriétés

  • Les quatre paramètres (v,k,λ,μ) vérifient toujours la relation suivante :
(vk − 1)μ = k(k − λ − 1)
  • Un graphe fortement régulier de type (v,k,λ,μ) a exactement trois valeurs propres distinctes :
    • k avec multiplicité 1
    • \frac{1}{2}\left[(\lambda-\mu)+\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}\right] avec multiplicité \frac{1}{2} \left[(v-1)-\frac{2k+(v-1)(\lambda-\mu)}{\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}}\right]
    • \frac{1}{2}\left[(\lambda-\mu)-\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}\right] avec multiplicité \frac{1}{2} \left[(v-1)+\frac{2k+(v-1)(\lambda-\mu)}{\sqrt{(\lambda-\mu)^2 + 4(k-\mu)}}\right]
  • Les graphes fortement réguliers dont les paramètres vérifient 2k + (v − 1)(λ − μ) = 0 sont nommés graphes de conférence à cause de leur relation avec les matrices de conférence. Leur type est \left(v, \frac{v-1}{2}, \frac{v-5}{4}, \frac{v-1}{4}\right).
  • Le graphe complémentaire d'un graphe fortement régulier de type (v,k,λ,μ) est aussi fortement régulier, de type (v, v−k−1, v−2−2k+μ, v−2k+λ).

Exemples


Wikimedia Foundation. 2010.

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

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • 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 de Clebsch — Représentation du graphe de Clebsch Nombre de sommets 16 Nombre d arêtes 40 Distribution des degrés 5 régulier Rayon …   Wikipédia en Français

  • Graphe de McLaughlin — Nombre de sommets 275 Nombre d arêtes 15 400 Distribution des degrés 112 régulier Rayon 2 Diamètre 2 Maille 3 Automorphismes 1 796 256 000 …   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 Schläfli — Représentation du graphe de Schläfli. Nombre de sommets 27 Nombre d arêtes 216 Distribution des degrés 16 régulier Rayon 2 …   Wikipédia en Français

  • Graphe local de McLaughlin — Représentation du graphe local de McLaughlin. Nombre de sommets 162 Nombre d arêtes 4 536 Distribution des degrés 56 régulier Rayon …   Wikipédia en Français

  • Graphe de Brouwer-Haemers — Représentations du graphe de Brouwer Haemers. Nombre de sommets 81 Nombre d arêtes 810 Distribution des degrés 20 régulier Rayon …   Wikipédia en Français

  • Graphe régulier — En théorie des graphes, un graphe régulier est un graphe où tous les sommets ont le même nombre de voisins, c est à dire le même degré ou valence. Un graphe régulier dont les sommets sont de degré k > est appelé un graphe k régulier ou graphe… …   Wikipédia en Français

Share the article and excerpts

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