У теорії графів граф Голднера — Харарі — це простий неорієнтований граф із 11 вершинами і 27 ребрами. Файл названо на честь А. Голднера і Ф. Харарі, які 1975 року довели, що він є найменшим негамільтоновим максимальним планарним графом... Ґрюнбаум 1967 року вже наводив той самий граф як приклад негамільтонового симпліційного многогранника..
Властивості Граф Голднера — Харарі планарний — його можна намалювати на площині без схрещень ребер. При малюванні на площині всі грані графа трикутні, що робить його максимальним планарним графом. Як і будь-який максимальний планарний граф, він також 3-вершинно-зв'язний — видалення будь-яких двох вершин залишає підграф зв'язним.
Граф Голднера — Харарі негамільтонів. Найменша кількість вершин для негамільтонових поліедральних графів дорівнює 11. Таким чином, граф Голднера — Харарі є прикладом мінімального графа цього типу. Однак граф Гершеля, інший негамільтонів граф із 11 вершинами, має менше ребер.
Як максимальний планарний граф негамільтонів, граф Голднера — Харарі є прикладом планарного з книжковою товщиною, більшою 2.. Ґрунтуючись на існуванні таких прикладів, Бернгарт і Кайнен (Bernhart, Kainen) висловили гіпотезу, що книжкова товщина планарних графів може бути довільно великою, але потім було показано книжкова товщина планарних графів не перевищує 4..
Книжкова товщина графа — 3, хроматичне число — 4, хроматичний індекс — 8, обхват — 3, радіус — 2, діаметр — 2 і граф є 3-реберно-зв'язним.
Граф є також 3-деревом, а тому його деревна ширина дорівнює 3. Подібно до будь-якого k-дерева, граф є хордальним. Як планарне 3-дерево, граф є прикладом мережі Аполлонія.
Геометрія За теоремою Штайніца граф Голднера — Харарі є поліедральним графом — він планарний і 3-зв'язний, так що існує опуклий многогранник, для якого граф Голднера — Харарі є кістяком.
Геометрично подання графа Голднера — Харарі у вигляді многогранника можна утворити, приклеївши тетраедр до кожної грані трикутної біпіраміди, так само, як триакістетраедр утворено приклеюванням тетраедра до кожної гранні октаедра. Тобто це многогранник Клі трикутної дипіраміди.. Двоїстий граф графа Голднера — Харарі геометрично подається зрізанням трикутної призми.
Алгебричні властивості Група автоморфізмів графа Голднера — Харарі має порядок 12 і ізоморфна діедральній групі D6, групі симетрій правильного шестикутника, що включає як обертання, так і відображення.
Характеристичний многочлен графа Голднера — Харарі дорівнює .
Примітки
Посилання