Граф Гевирца — это сильно регулярный граф с 56 вершинами и валентностью 10. Граф назван именем математика Аллана Гевирца, описавшего граф в своей диссертации.
Построение
Граф Гевирца можно построить следующим образом. Рассмотрим единственную систему Штейнера S ( 3 , 6 , 22 ) {displaystyle S(3,6,22)} с 22 элементами и 77 блоками. Выберем произвольный элемент и будем считать вершинами 56 блоков, не связанных с этим элементом. Соединяем ребром два блока, если они не пересекаются.
По этому построению можно вложить граф Гевирца в граф Хигмана — Симса.
Свойства
Характеристический многочлен графа Гевирца равен
( x − 10 ) ( x − 2 ) 35 ( x + 4 ) 20 . {displaystyle (x-10)(x-2)^{35}(x+4)^{20}.,}Поэтому граф является целым графом — графом, спектр которого полностью состоит из целых чисел. Граф Гевирца полностью определён своим спектром.
Число независимости графа равно 16.