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

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

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

Властивості

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

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

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

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

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

Геометрія

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

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

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

Група автоморфзмів графа Голднера — Харарі має порядок 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.