Граф Гевирца
Граф Гевирца | |
---|---|
Назван в честь | Аллана Гевирца |
Вершин | 56 |
Рёбер | 280 |
Диаметр | 2 |
Обхват | 4 |
Автоморфизмы | 80640 |
Хроматическое число | 4 |
Свойства |
Сильно регулярный Гамильтонов Без треугольников Вершинно-транзитивный Рёберно-транзитивный Дистанционно-транзитивный |
Граф Гевирца — это сильно регулярный граф с 56 вершинами и валентностью 10. Граф назван именем математика Аллана Гевирца, описавшего граф в своей диссертации[1].
Построение
Граф Гевирца можно построить следующим образом. Рассмотрим единственную систему Штейнера [math]\displaystyle{ S(3, 6, 22) }[/math] с 22 элементами и 77 блоками. Выберем произвольный элемент и будем считать вершинами 56 блоков, не связанных с этим элементом. Соединяем ребром два блока, если они не пересекаются.
По этому построению можно вложить граф Гевирца в граф Хигмана — Симса.
Свойства
Характеристический многочлен графа Гевирца равен
- [math]\displaystyle{ (x-10)(x-2)^{35}(x+4)^{20}. \, }[/math]
Поэтому граф является целым графом — графом, спектр которого полностью состоит из целых чисел. Граф Гевирца полностью определён своим спектром.
Число независимости графа равно 16.
Примечания
- ↑ Allan Gewirtz. Graphs with Maximal Even Girth. — City University of New York, 1967. — (Ph.D. Dissertation in Mathematics). Архивная копия от 31 января 2019 на Wayback Machine
Литература
- Brouwer, Andries. Sims-Gewirtz graph . Дата обращения: 30 января 2019. Архивировано 31 января 2019 года.
- Weisstein, Eric W. Gewirtz graph (англ.) на сайте Wolfram MathWorld.
Для улучшения этой статьи желательно: |