Graphes de Chang
Dans le domaine mathématique de la théorie des graphes, les graphes de Chang sont trois graphes non orientés réguliers, chacun avec 28 sommets et 168 arêtes. Ce sont des graphes fortement réguliers, ils ont les mêmes paramètres et mêmes spectres que le Line graph du graphe complet . Ils sont pancycliques.
| Graphe de Chang | |
 À droite les trois graphes de Chang à droite ; à gauche les ensembles d'échanges engendrés à partir du line graph . | |
| Nombre de sommets | 28 |
|---|---|
| Nombre d'arêtes | 168 |
| Rayon | 2 |
| Diamètre | 2 |
| Maille | 3 |
| Propriétés | fortement régulier |
modifier  |
|
Chacun de ces trois graphes peut être obtenu par « complémentation » de graphe à partir de : on choisit un sous-ensemble S de sommets de , on supprime les arêtes qui relient un sommet dans S et un sommet qui n'est pas dans S et on ajoute une arête pour chaque paire de sommets (avec l'un dans S et l'autre non ) qui n'étaient pas déjà reliés par une arête. Parmi les graphes qui peuvent être ainsi engendrés de cette façon, trois sont les graphes de Chang.
Les graphes de Chang portent le nom de Chang Li-Chien qui a prouvé qu'à ces exceptions près tout line graph d'un graphe complet est déterminé de manière unique par ses paramètres en tant que graphe fortement régulier[1].
Voir aussi
modifier- Premier graphe de Chang
- Second graphe de Chang
- Troisième graphe de Chang
- Graphe de Shrikhande, une exception similaire à l'unicité des graphes fortement réguliers .
Références
modifier- Chang Li-Chien, « The uniqueness and non-uniqueness of the triangular association schemes », Science Record, New Series, vol. 3, , p. 604–613 (zbMATH 0089.15102).
