Граф Гофмана — 4-регулярний граф із 16 вершинами та 32 ребрами, який відкрив  і опублікував 1963 року. Граф коспектральний графу гіперкуба Q4.

Граф Гофмана має багато спільних властивостей з гіперкубом Q4 — обидва гамільтонові і мають хроматичне число 2, хроматичний індекс 4, обхват 4 і діаметр 4. Граф також 4-вершинно-зв'язний і 4-реберно-зв'язний. Проте радіус графа Гофмана дорівнює 3 на відміну від гіперкуба Q4, радіус якого дорівнює 4. Граф Гофмана не є дистанційно-регулярним. Граф має книжкову товщину 3 та число черг 2.

Алгебричні властивості
Граф Гофмана не є вершинно-транзитивним і його повна група автоморфізмів є групою порядку 48, ізоморфною прямому добутку симетричної групи S4 і циклічної групи Z/2Z.

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

:  ,

що робить його цілим графом — графом, спектр якого складається тільки з цілих чисел. Це той самий спектр, що й у гіперкуба Q4.

Галерея


Примітки



