Графы Чана

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

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

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

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

См. также

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

Примечания

Chang, 1959, с. 604–613.

Литература

Chang Li-Chien. The uniqueness and non-uniqueness of the triangular association schemes // Science Record (Peking). — 1959. — Т. 3.

Ссылки

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[_16f9ed82754a7e19-1] Chang, 1959, с. 604–613.