Граф Гофмана

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

Граф Гофмана
Названо на честь
(Вершин)	16
(Ребер)	32
(Радіус)	3
(Діаметр)	4
(Обхват)	4
(Автоморфізм)	48 (${\displaystyle \mathbb {Z} /2\mathbb {Z} \times S_{4}}$)
Хроматичне число	2
Хроматичний індекс	4
Число черг	2
Властивості	гамільтонів двочастковий досконалий ейлерів

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

Алгебричні властивості

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

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

${\displaystyle (x-4)(x-2)^{4}x^{6}(x+2)^{4}(x+4)}$ ,

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

Галерея

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

Примітки

1. Weisstein, Eric W. Hoffman graph(англ.) на сайті Wolfram MathWorld.
2. Hoffman A. J. On the Polynomial of a Graph // Amer. Math. Monthly. — 1963. — Т. 70. — С. 30-36.
3. van Dam E. R., Haemers W. H. Spectral Characterizations of Some Distance-Regular Graphs // J. Algebraic Combin.. — 2003. — Т. 15. — С. 189-202.
4. Jessica Wolz. Engineering Linear Layouts with SAT. — University of Tübingen, 2018. — (Master Thesis).