Граф Голднера — Харарі
У теорії графів граф Голднера — Харарі — це простий неорієнтований граф із 11 вершинами і 27 ребрами. Файл названо на честь А. Голднера і Ф. Харарі, які 1975 року довели, що він є найменшим негамільтоновим максимальним планарним графом[1][2]. Ґрюнбаум 1967 року вже наводив той самий граф як приклад негамільтонового симпліційного многогранника[3].
| Граф Голднера — Харарі | |
|---|---|
 | |
| Названо на честь | А. Голднер, Ф. Харарі |
| Вершин | 11 |
| Ребер | 27 |
| Радіус | 2 |
| Діаметр | 2 |
| Обхват | 3 |
| Автоморфізм | 12 (D6) |
| Хроматичне число | 4 |
| Хроматичний індекс | 8 |
| Властивості |
поліедральний
деревна ширина = 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 і ізоморфна діедральній групі D6, групі симетрій правильного шестикутника, що включає як обертання, так і відображення.
Характеристичний многочлен графа Голднера — Харарі дорівнює .
Примітки ред.
- ↑ M. B. Dillencourt. Polyhedra of small orders and their Hamiltonian properties // Journal of Combinatorial Theory, Series B. — 1996. — Т. 66. — С. 87–122. — DOI:..
- ↑ R. C. Read, R. J. Wilson. An Atlas of Graphs. — Oxford, England : Oxford University Press, 1998. — С. 285..
- ↑ а б Branko Grünbaum. Convex Polytopes. — Wiley Interscience, 1967. — С. 357..
- ↑ Frank R. Bernhart, Paul C. Kainen. The book thickness of a graph. — Journal of Combinatorial Theory, Series B. — 1979. — Т. 27. — С. 320–331. — DOI:.
- ↑ Mihalis Yannakakis. Proc. 18th ACM Symp. Theory of Computing (STOC). — 1986. — С. 104–108. — DOI:.
- ↑ Günter Ewald. Hamiltonian circuits in simplicial complexes // Geometriae Dedicata. — 1973. — Т. 2, вип. 1. — С. 115–125. — DOI:..
Посилання ред.
- Weisstein, Eric W. Граф Голднера — Харарі(англ.) на сайті Wolfram MathWorld.