График Гевирца - Википедия - Gewirtz graph

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

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

Строительство

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

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

Характеристики

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

Следовательно, это интегральный график. Граф Гевиртца также определяется своим спектром.

В число независимости 16 лет.

Примечания

  1. ^ Аллан Гевиртц, Графики с максимальным четным обхватом, Кандидат наук. Диссертация по математике, Городской университет Нью-Йорка, 1967.

Рекомендации

  • Брауэр, Андрис. «График Симса-Гевирца».
  • Вайсштейн, Эрик В. «График Гевирца». MathWorld.