Граф Голднера — Харари

Граф Голднера — Харари
Назван в честь	А. Голднер, Ф. Харари
Вершин	11
Рёбер	27
Радиус	2
Диаметр	2
Обхват	3
Автоморфизмы	12 (D6)
Хроматическое число	4
Хроматический индекс	8
Свойства	полиэдральный планарный хордальный совершенный древесная ширина = 3
Медиафайлы на Викискладе

В теории графов Граф Голднера — Харари — это простой неориентированный граф с 11 вершинами и 27 рёбрами. Файл назван в честь А. Голднера и Ф. Харари, которые в 1975 году доказали, что он является наименьшим негамильтоновым максимальным планарным графом. Тот же самый граф был уже приведён в качестве примера негамильтонова симплициального многогранника Грюнбаумом в 1967.

Свойства

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

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

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

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

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

Геометрия

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

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

Алгебраические свойства

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

Характеристический многочлен графа Голднера — Харари равен $-(x-1)^{2}x^{2}(x+2)^{3}(x^{2}-3)(x^{2}-4x-9)$.

Ссылки

• Weisstein, Eric W. Goldner-Harary graph (англ.) на сайте Wolfram MathWorld.