Graphe fortement régulier
# Graphe fortement régulier

En théorie des graphes, qui est un domaine des mathématiques, un graphe fortement régulier est un type de graphe régulier.

## Définition

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.

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.

## Propriétés

Familles de graphes définies par leurs automorphismes :

| distance-transitif | → | distance-régulier | ← | fortement régulier |
| - | - | - | - | - |
| symétrique (arc-transitif) | ← | t-transitif, (t ≥ 2) | | symétrique gauche (en) |
| $_{(siconnexe)}$ sommet-transitif et arête-transitif | → | régulier et arête-transitif | → | arête-transitif |
| sommet-transitif | → | régulier | → | $_{(sibiparti)}$ birégulier |
| graphe de Cayley | ← | zéro-symétrique | | asymétrique |

* 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]$
* Les graphes fortement réguliers dont les paramètres vérifient $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 $\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

* 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).
