Граф Гевірца
Перейти до навігації
Перейти до пошуку
Граф Гевірца | |
---|---|
![]() Деякі вкладення з 7-кратною симетрією. 8- або 14-кратні симетрії неможливі. | |
Вершин | 56 |
Ребер | 280 |
Радіус | 2 |
Діаметр | 2 |
Обхват | 4 |
Автоморфізм | 80 640 |
Хроматичне число | 4 |
Властивості |
сильно регулярний гамільтонів без трикутників вершинно-транзитивний реберно-транзитивний дистанційно-транзитивний |
Граф Гевірца — сильно регулярний граф з 56 вершинами та валентністю 10. Граф названо ім'ям математика Аллана Гевірца (Allan Gewirtz), який описав граф у своїй дисертації[1].
Граф Гевірца можна побудувати в такий спосіб. Розглянемо єдину систему Штейнера з 22 елементами та 77 блоками. Виберемо довільний елемент і вважатимемо вершинами 56 блоків, пов'язаних із цим елементом. З'єднуємо ребром два блоки, якщо вони не перетинаються.
За цією побудовою можна вкласти граф Гевірца в граф Гіґмана — Сімса.
Характеристичний многочлен графа Гевірца дорівнює
Тому граф є цілим графом — графом, спектр якого складається лише з цілих чисел. Граф Гевірца повністю визначений своїм спектром.
Число незалежності графа дорівнює 16.
- ↑ 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.