Граф Гевірца

Граф Гевірца — сильно регулярний граф з 56 вершинами та валентністю 10. Граф названо ім'ям математика Аллана Гевірца (Allan Gewirtz), який описав граф у своїй дисертації.

Граф Гевірца
Деякі вкладення з 7-кратною симетрією. 8- або 14-кратні симетрії неможливі.
(Вершин)	56
(Ребер)	280
(Радіус)	2
(Діаметр)	2
(Обхват)	4
(Автоморфізм)	80 640
Хроматичне число	4
Властивості	сильно регулярний гамільтонів без трикутників вершинно-транзитивний реберно-транзитивний дистанційно-транзитивний

Побудова

Граф Гевірца можна побудувати в такий спосіб. Розглянемо єдину систему Штейнера ${\displaystyle S(3,6,22)}$ з 22 елементами та 77 блоками. Виберемо довільний елемент і вважатимемо вершинами 56 блоків, пов'язаних із цим елементом. З'єднуємо ребром два блоки, якщо вони не перетинаються.

За цією побудовою можна вкласти граф Гевірца в граф Гіґмана — Сімса.

Властивості

Характеристичний многочлен графа Гевірца дорівнює

${\displaystyle (x-10)(x-2)^{35}(x+4)^{20}.\,}$

Тому граф є цілим графом — графом, спектр якого складається лише з цілих чисел. Граф Гевірца повністю визначений своїм спектром.

Число незалежності графа дорівнює 16.

Примітки

1. Allan Gewirtz. Graphs with Maximal Even Girth. — City University of New York, 1967. — (Ph.D. Dissertation in Mathematics)

Література

• Brouwer, Andries. Sims-Gewirtz graph. оригіналу за 31 січня 2019. Процитовано 30 січня 2019.
• Weisstein, Eric W. Граф Гевірца(англ.) на сайті Wolfram MathWorld.