Graphe de Chang
À droite les trois graphes de Chang à droite ; à gauche les ensembles d'échanges engendrés à partir du line graph ${\displaystyle L(K_{8})}$.
Nombre de sommets	28
Nombre d'arêtes	168
Rayon	2
Diamètre	2
Maille	3
Propriétés	fortement régulier
modifier

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 ${\displaystyle L(K_{8})}$ du graphe complet ${\displaystyle K_{8}}$. Ils sont pancycliques.

Chacun de ces trois graphes peut être obtenu par « complémentation » de graphe à partir de ${\displaystyle L(K_{8})}$ : on choisit un sous-ensemble S de sommets de ${\displaystyle 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^[1].

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

• (en) Eric W. Weisstein, « Chang Graphs », sur MathWorld
• Andries E. Brouwer, « Les graphes de Chang »
• Nadia Hamoud, « Les graphes de Chang »

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