Графи Чана

Графи Чана — це набір із трьох 12-регулярних неорієнтованих графів, кожен із 28 вершинами та 168 ребрами. Усі вони сильно регулярні і мають такі ж параметри та спектр, як і реберний граф $L(K_8)$ повного графа $K_8$. Графи Чана названо ім'ям Лі-Чієна Чана (Шаблон:Lang-en), який довів, що, за винятком цих трьох графів, будь-який реберний граф повного графа єдиним чином визначається його параметрами сильно регулярного графаШаблон: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Шаблон:Бібліоінформація