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.
Le graphe de Paley d'ordre 13, un graphe fortement régulier de type (13,6,2,3).
DĂ©finition
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.
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) | |
â | ||||
(si connexe) sommet-transitif et arĂȘte-transitif |
â | rĂ©gulier et arĂȘte-transitif | â | arĂȘte-transitif |
â | â | â | ||
sommet-transitif | â | rĂ©gulier | â | (si biparti) birĂ©gulier |
â | ||||
graphe de Cayley | â | zĂ©ro-symĂ©trique | asymĂ©trique |
- Les quatre paramĂštres (v,k,λ,ÎŒ) vĂ©rifient toujours la relation suivante :
- Un graphe fortement rĂ©gulier de type (v,k,λ,ÎŒ) a exactement trois valeurs propres distinctes :
- avec multiplicité 1
- avec multiplicité
- avec multiplicité
- Les graphes fortement réguliers dont les paramÚtres vérifient sont nommés graphes de conférence à cause de leur relation avec les matrices de conférence. Leur type est .
- 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).
Notes et références
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplĂ©mentaires peuvent sâappliquer aux fichiers multimĂ©dias.