Accueil🇫🇷Chercher

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
Image illustrative de l’article Graphes 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

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

Références

  1. 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).

Liens externes

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