Graphe fortement régulier

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
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[modifier | modifier le code]

  • Les quatre paramètres (v,k,λ,μ) vérifient toujours la relation suivante :
(v-k-1)\mu = k(k-\lambda-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]
  • 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[modifier | modifier le code]