Граф Гофмана — 4-регулярний граф із 16 вершинами та 32 ребрами, який відкрив і опублікував 1963 року. Граф коспектральний графу гіперкуба Q4.
Граф Гофмана має багато спільних властивостей з гіперкубом Q4 — обидва гамільтонові і мають хроматичне число 2, хроматичний індекс 4, обхват 4 і діаметр 4. Граф також 4-вершинно-зв'язний і 4-реберно-зв'язний. Проте радіус графа Гофмана дорівнює 3 на відміну від гіперкуба Q4, радіус якого дорівнює 4. Граф Гофмана не є дистанційно-регулярним. Граф має книжкову товщину 3 та число черг 2.
Алгебричні властивості Граф Гофмана не є вершинно-транзитивним і його повна група автоморфізмів є групою порядку 48, ізоморфною прямому добутку симетричної групи S4 і циклічної групи Z/2Z.
Характеристичний многочлен графа Гофмана дорівнює
,
що робить його цілим графом — графом, спектр якого складається тільки з цілих чисел. Це той самий спектр, що й у гіперкуба Q4.
Галерея
Примітки