Graphes de Chang

Modèle:Infobox Graphe 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 $L(K_8)$ du graphe complet $K_8$. Ils sont pancycliques.

Chacun de ces trois graphes peut être obtenu par « complémentation » de graphe à partir de $L(K_8)$ : on choisit un sous-ensemble S de sommets de $L(K_8)$, 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.

Voir aussi

• 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 $L(K_{8,8})$.

Liens externes

• Modèle:MathWorld
• Andries E. Brouwer, « Les graphes de Chang »
• Nadia Hamoud, « Les graphes de Chang »