Графы Чана — это набор из трёх 12-регулярных неориентированных графов, каждый из которых содержит 28 вершин и 168 рёбер. Все они сильно регулярны и имеют те же параметры и спектр, что и рёберный граф L(K8) полного графа K8. Графы Чана названы в честь математика Ли-Чиена Чана, который доказал, что, за исключением этих трёх графов, любой рёберный граф полного графа единственным образом определяется его параметрами сильно регулярного графа.
Связь с графами L(K8) Каждый из этих трёх графов может быть получен переключением графа из . Это означает, что выбирается подмножество S вершин графа . Каждое ребро, которое соединяет вершину из S с вершиной, не принадлежащей S, в графе , удаляется, и добавляются рёбра для каждой пары вершин (одна принадлежит S, а другая не принадлежит), которые ранее не были соединены ребром. Среди графов, которые могут быть образованы таким образом, находятся графы Чана.
См. также Граф Шрикханде, похожее исключение единственности параметров сильно регулярных графов
Примечания
Литература
Ссылки Weisstein, Eric W. "Chang Graphs." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/ChangGraphs.html Andries E. Brouwer's page on Chang graphs Nadia Hamoud, "The Chang graphs"
Категория:Сильно регулярные графы Категория:Графы, имеющие собственные названия