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