Графы Чана

графы Чана
Три графа Чана (справа) и переключающие множества, генерирующие их из рёберного графа L(K8) (зелёные вершины слева)
Назван в честь	Ли-Чиена Чана
Вершин	28
Рёбер	168
Радиус	2
Диаметр	2
Обхват	3
Автоморфизмы	96360384
Свойства	Сильно регулярный
Медиафайлы на Викискладе

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

Связь с графами ${\displaystyle L(K_{8})}$

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

См. также

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

Примечания

Литература

Ссылки

• Weisstein, Eric W. "Chang Graphs." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/ChangGraphs.html Архивная копия от 28 января 2019 на Wayback Machine
• Andries E. Brouwer's page on Chang graphs Архивная копия от 11 апреля 2018 на Wayback Machine
• Nadia Hamoud, "The Chang graphs" Архивная копия от 29 августа 2017 на Wayback Machine

Эта страница в последний раз была отредактирована 31 января 2024 в 16:58.