Граф Гевирца

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

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

ПостроениеПравить

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

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

СвойстваПравить

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

$(x-<!--\; -\; -->10)(x-<!--\; -\; -->2{)}^{35}(x+4{)}^{20}.$$(x-10)(x-2)^{35}(x+4)^{20}.\,$ 

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

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

ЛитератураПравить

• Brouwer, Andries. Sims-Gewirtz graph  (неопр.). Дата обращения: 30 января 2019. Архивировано 31 января 2019 года.
• Weisstein, Eric W. Gewirtz graph (англ.) на сайте Wolfram MathWorld.