WikiSort.ru - Не сортированное

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

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

Свойства

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

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

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

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

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

Геометрия

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

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

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

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

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

Примечания

Ссылки

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

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии.