Граф Гевирца

Граф Гевирца — это сильно регулярный граф с 56 вершинами и валентностью 10. Граф назван именем математика Аллана Гевирца, описавшего граф в своей диссертации[1].

Граф Гевирца

Некоторые вложения с 7-кратной симметрией. 8-кратные или 14-кратные симметрии невозможны
Назван в честь Аллана Гевирца
Вершин 56
Рёбер 280
Диаметр 2
Обхват 4
Автоморфизмы 80640
Хроматическое число 4
Свойства Сильно регулярный
Гамильтонов
Без треугольников
Вершинно-транзитивный
Рёберно-транзитивный
Дистанционно-транзитивный
 Медиафайлы на Викискладе

Построение

Граф Гевирца можно построить следующим образом. Рассмотрим единственную систему Штейнера с 22 элементами и 77 блоками. Выберем произвольный элемент и будем считать вершинами 56 блоков, не связанных с этим элементом. Соединяем ребром два блока, если они не пересекаются.

По этому построению можно вложить граф Гевирца в граф Хигмана — Симса.

Свойства

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

Поэтому граф является целым графом — графом, спектр которого полностью состоит из целых чисел. Граф Гевирца полностью определён своим спектром.

Число независимости графа равно 16.

Примечания

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

Литература

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