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 ${\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].

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.