Граф Голднера — Харарі

У теорії графів граф Голднера — Харарі — це простий неорієнтований граф із 11 вершинами і 27 ребрами. Файл названо на честь А. Голднера і Ф. Харарі, які 1975 року довели, що він є найменшим негамільтоновим максимальним планарним графом. Ґрюнбаум 1967 року вже наводив той самий граф як приклад негамільтонового симпліційного многогранника.

Граф Голднера — Харарі
Названо на честь	А. Голднер, Ф. Харарі
(Вершин)	11
(Ребер)	27
(Радіус)	2
(Діаметр)	2
(Обхват)	3
(Автоморфізм)	12 (D6)
Хроматичне число	4
Хроматичний індекс	8
Властивості	поліедральний планарний хордальний досконалий деревна ширина = 3

Властивості

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

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

Як максимальний планарний граф негамільтонів, граф Голднера — Харарі є прикладом планарного з книжковою товщиною, більшою 2. Ґрунтуючись на існуванні таких прикладів, Бернгарт і Кайнен (Bernhart, Kainen) висловили гіпотезу, що книжкова товщина планарних графів може бути довільно великою, але потім було показано книжкова товщина планарних графів не перевищує 4.

Книжкова товщина графа — 3, хроматичне число — 4, хроматичний індекс — 8, обхват — 3, радіус — 2, діаметр — 2 і граф є 3-реберно-зв'язним.

Граф є також 3-деревом, а тому його деревна ширина дорівнює 3. Подібно до будь-якого k-дерева, граф є хордальним. Як планарне 3-дерево, граф є прикладом мережі Аполлонія.

Геометрія

За теоремою Штайніца граф Голднера — Харарі є поліедральним графом — він планарний і 3-зв'язний, так що існує опуклий многогранник, для якого граф Голднера — Харарі є (кістяком).

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

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

Група автоморфзмів графа Голднера — Харарі має порядок 12 і ізоморфна діедральній групі D₆, групі симетрій правильного шестикутника, що включає як обертання, так і відображення.

Характеристичний многочлен графа Голднера — Харарі дорівнює ${\displaystyle -(x-1)^{2}x^{2}(x+2)^{3}(x^{2}-3)(x^{2}-4x-9)}$ .

Примітки

1. M. B. Dillencourt. Polyhedra of small orders and their Hamiltonian properties // Journal of Combinatorial Theory, Series B. — 1996. — Т. 66. — С. 87–122. — DOI:10.1006/jctb.1996.0008..
2. R. C. Read, R. J. Wilson. An Atlas of Graphs. — Oxford, England : Oxford University Press, 1998. — С. 285..
3. Branko Grünbaum. Convex Polytopes. — Wiley Interscience, 1967. — С. 357..
4. Frank R. Bernhart, Paul C. Kainen. The book thickness of a graph. — Journal of Combinatorial Theory, Series B. — 1979. — Т. 27. — С. 320–331. — DOI:10.1016/0095-8956(79)90021-2..
5. Mihalis Yannakakis. Proc. 18th ACM Symp. Theory of Computing (STOC). — 1986. — С. 104–108. — DOI:10.1145/12130.12141..
6. Günter Ewald. Hamiltonian circuits in simplicial complexes // Geometriae Dedicata. — 1973. — Т. 2, вип. 1. — С. 115–125. — DOI:10.1007/BF00149287..

Посилання

• Weisstein, Eric W. Граф Голднера — Харарі(англ.) на сайті Wolfram MathWorld.