Loading AI tools
простий неорієнтований граф із 11 вершинами і 27 ребрами З Вікіпедії, вільної енциклопедії
У теорії графів граф Голднера — Харарі — це простий неорієнтований граф із 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, групі симетрій правильного шестикутника, що включає як обертання, так і відображення.
Характеристичний многочлен графа Голднера — Харарі дорівнює .
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.