Graphe fortement régulier

Soit G = (V,E) un graphe régulier ayant v sommets et degré k. On dit que G est fortement régulier[1] 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.

Un 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.

• Les quatre paramètres (v,k,λ,μ) vérifient toujours la relation suivante :

${\displaystyle (v-k-1)\mu =k(k-\lambda -1)}$

• Un graphe fortement régulier de type (v,k,λ,μ) a exactement trois valeurs propres distinctes :
  • ${\displaystyle k}$ avec multiplicité 1
  • ${\displaystyle {\frac {1}{2}}\left[(\lambda -\mu )+{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\right]}$ avec multiplicité ${\displaystyle {\frac {1}{2}}\left[(v-1)-{\frac {2k+(v-1)(\lambda -\mu )}{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}}\right]}$
  • ${\displaystyle {\frac {1}{2}}\left[(\lambda -\mu )-{\sqrt {(\lambda -\mu )^{2}+4(k-\mu )}}\right]}$ avec multiplicité ${\displaystyle {\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 ${\displaystyle 2k+(v-1)(\lambda -\mu )=0}$ sont nommés graphes de conférence à cause de leur relation avec les matrices de conférence. Leur type est ${\displaystyle \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+λ).

• Le graphe de Shrikhande de type (16,6,2,2).
• Le cycle de longueur 5, de type (5,2,0,1).
• Le graphe de Petersen de type (10,3,0,1).
• Les graphes de Chang de type (28,12,6,4).
• Le graphe de Hoffman-Singleton de type (50,7,0,1).
• Le graphe de Higman-Sims de type (100,22,0,6).
• Le graphe de Paley d'ordre q dont le type est (q, (q − 1)/2, (q − 5)/4, (q − 1)/4.
• Le graphe de Brouwer-Haemers de type (81,20,1,6).
• Le graphe de Schläfli de type (27,16,10,8).
• Le graphe local de McLaughlin de type (162,56,10,24).

• Portail de l'informatique théorique
• Portail des mathématiques