Граф Гевірца

Шаблон:Граф Граф Гевірца — сильно регулярний граф з 56 вершинами та валентністю 10. Граф названо ім'ям математика Аллана Гевірца (Шаблон:Lang), який описав граф у своїй дисертації.

Побудова

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

За цією побудовою можна вкласти граф Гевірца в граф Гіґмана — Сімса.

Властивості

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

$(x-10)(x-2{)}^{35}(x+4{)}^{20}.$

Тому граф є цілим графом — графом, спектр якого складається лише з цілих чисел. Граф Гевірца повністю визначений своїм спектром.

Число незалежності графа дорівнює 16.

Література

• Шаблон:Cite web
• Шаблон:MathWorld