В математической области теории графов граф Голднера–Харари — это простой неориентированный граф с 11 вершинами и 27 рёбрами. Он назван в честь А. Голднера и Фрэнка Харари , которые в 1975 году доказали, что это наименьший негамильтонов максимальный планарный граф . [1] [2] [3] Этот же граф уже был приведён в качестве примера негамильтонова симплициального многогранника Бранко Грюнбаумом в 1967 году. [4]
Граф Голднера–Харари является планарным графом : его можно нарисовать на плоскости, не пересекая ни одно ребро. При изображении на плоскости все его грани треугольные, что делает его максимальным планарным графом . Как и любой максимальный планарный граф, он также является 3-вершинно-связным : удаление любых двух его вершин оставляет связный подграф .
Граф Голднера–Харари также негамильтонов . Наименьшее возможное число вершин для негамильтонова полиэдрального графа равно 11. Поэтому граф Голднера–Харари является минимальным примером графов этого типа. Однако граф Гершеля , другой негамильтонов полиэдр с 11 вершинами, имеет меньше ребер.
Как негамильтонов максимальный планарный граф, граф Голднера–Харари представляет собой пример планарного графа с книжной толщиной больше двух. [5] Основываясь на существовании таких примеров, Бернхарт и Кайнен предположили, что книжная толщина планарных графов может быть сделана произвольно большой, но впоследствии было показано, что все планарные графы имеют книжную толщину не более четырех. [6]
Он имеет толщину 3, хроматическое число 4, хроматический индекс 8, обхват 3, радиус 2, диаметр 2 и является 3- рёберно-связным графом .
Это также 3-дерево , и поэтому его древовидная ширина равна 3. Как и любое k -дерево, это хордовый граф . Как планарное 3-дерево, оно образует пример аполлоновой сети .
По теореме Штейница граф Голднера–Харари является полиэдральным графом : он плоский и 3-связный, поэтому существует выпуклый многогранник, имеющий граф Голднера–Харари в качестве своего скелета .
Геометрически многогранник, представляющий граф Голднера–Харари, может быть образован путем приклеивания тетраэдра к каждой грани треугольной дипирамиды , аналогично тому, как триакисоктаэдр образуется путем приклеивания тетраэдра к каждой грани октаэдра . То есть, это вершина Клеетопа треугольной дипирамиды. [4] [7] Двойственный граф графа Голднера–Харари геометрически представлен усечением треугольной призмы .
Группа автоморфизмов графа Голднера–Харари имеет порядок 12 и изоморфна диэдральной группе D 6 , группе симметрий правильного шестиугольника , включая как вращения, так и отражения.
Характеристический многочлен графа Голднера–Харари равен: .
