Графы Чана

Графы Чана — набор из трёх 12-регулярных неориентированных графов, каждый с 28 вершинами и 168 рёбрами. Все они сильно регулярны и имеют те же параметры и спектр, что и рёберный граф L(K₈) полного графа K₈. Графы Чана названы именем Ли-Чиена Чана, который доказал, что, за исключением этих трёх графов, любой рёберный граф полного графа единственным образом определяется его параметрами сильно регулярного графаШаблон:Sfn.

Связь с графами L(K₈)

Каждый из этих трёх графов может быть получен переключением графа из $L(K_8)$. То есть выбирается подмножество S вершин графа $L(K_8)$, каждое ребро, которое соединяет вершину из S с вершиной не из S в графе $L(K_8)$, удаляется и добавляются рёбра для каждой пары вершин (снова одна принадлежит S, а другая не принадлежит), которые ранее не были соединены ребром. Среди графов, которые могут быть образованы таким образом, находятся графы Чана.

См. также

• Граф Шрикханде, похожее исключение единственности параметров сильно регулярных графов $L(K_n,n)$

Литература

• Шаблон:Статья

Ссылки

• Weisstein, Eric W. "Chang Graphs." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/ChangGraphs.html Шаблон:Wayback
• Andries E. Brouwer's page on Chang graphs Шаблон:Wayback
• Nadia Hamoud, "The Chang graphs" Шаблон:Wayback