В теории графов Граф Голднера — Харари — это простой неориентированный граф с 11 вершинами и 27 рёбрами. Назван в честь А. Голднера и Ф. Харари, которые в 1975 году доказали, что он является наименьшим негамильтоновым максимальным планарным графом. См. также номера 6(2):33 (1975) и 8:104-106 (1977). Ссылки с сайта список публикаций Харари .... Тот же самый граф был уже приведён в качестве примера негамильтонова симплициального многогранника Грюнбаумом в 1967.

Свойства Граф Голднера — Харари планарен — его можно нарисовать на плоскости без пересечения рёбер. При рисовании на плоскости все грани графа треугольны, что делает его максимальным планарным графом. Как и любой максимальный планарный граф, он является 3-вершинно связным — удаление любых двух вершин оставляет подграф связным.

Граф Голднера — Харари негамильтонов. Минимальное число вершин у негамильтонова полиэдрального графа равно 11. Таким образом, граф Голднера — Харари является примером минимального графа этого типа.Однако граф Хершеля — другой негамильтонов многогранник с 11 вершинами , имеет меньше рёбер.

Как максимальный планарный негамильтонов граф, граф Голднера — Харари даёт пример планарного графа с книжной толщиной, большей двух.. На основании существования подобных примеров Бернхарт и Кайнен выдвинули гипотезу, что книжная толщина планарных графов может быть произвольно большой, но затем было показано, что все планарные графы имеют книжную толщину, не превосходящую четырёх..

Книжная толщина графа равна 3, хроматическое число равно 4, хроматический индекс равен 8, длина наименьшего цикла (обхват) равна 3, радиус равен 2, диаметр равен 2 и граф является рёберно 3-связным.

Граф является также 3-деревом, а потому его древовидная ширина равна 3. Подобно любому k-дереву, граф является хордальным. Как планарное 3-дерево, граф даёт пример сети Аполлония.

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

Геометрически представление графа Голднера — Харари в виде многогранника может быть образовано путём склеивания тетраэдра к каждой грани треугольной дипирамиды, таким же образом, как триакистетраэдр образован склеиванием тетраэдра с каждой гранью октаэдра. Таким образом, он представляет собой многогранник Кли треугольной дипирамиды... Его двойственный граф геометрически соответствует усечённой треугольной призме

Алгебраические свойства Группа автоморфизмов графа Голднера — Харари имеет порядок 12 и изоморфна диэдрической группе D6, группе симметрий правильного шестиугольника, включающей как вращения, так и отражения.

Характеристический многочлен графа имеет вид .

Примечания

Ссылки

Категория:Графы, имеющие собственные названия Категория:Планарные графы