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

Перейти к навигацииПерейти к поиску
Граф Голднера — Харари
Назван в честь А. Голднер, Ф. Харари
Вершин 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-деревом, а потому его древесная ширина равно 3. Подобно любому k-дереву, граф является хордальным. Как планарное 3-дерево, граф даёт пример сети Аполлония.

Геометрия

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

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

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

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

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

Примечания

  1. ↑ A. Goldner, F. Harary. {{{заглавие}}} // Bull. Malaysian Math. Soc.. — 1975. — Т. 6, вып. 1. — С. 41–42.. См. также номера 6(2):33 (1975) и 8:104-106 (1977). Ссылки с сайта список публикаций Харари Архивная копия от 2 января 2013 на Wayback Machine.
  2. ↑ M. B. Dillencourt. Polyhedra of small orders and their Hamiltonian properties // Journal of Combinatorial Theory, Series B. — 1996. — Т. 66. — С. 87–122. — doi:10.1006/jctb.1996.0008..
  3. ↑ R. C. Read, R. J. Wilson. An Atlas of Graphs. — Oxford, England: Oxford University Press, 1998. — С. 285..
  4. ↑ 1 2 Branko Grünbaum. Convex Polytopes. — Wiley Interscience, 1967. — С. 357..
  5. ↑ Frank R. Bernhart, Paul C. Kainen. The book thickness of a graph. — Journal of Combinatorial Theory, Series B. — 1979. — Т. 27. — С. 320–331. — doi:10.1016/0095-8956(79)90021-2..
  6. ↑ Mihalis Yannakakis. Proc. 18th ACM Symp. Theory of Computing (STOC). — 1986. — С. 104–108. — doi:10.1145/12130.12141..
  7. ↑ Günter Ewald. Hamiltonian circuits in simplicial complexes // Geometriae Dedicata. — 1973. — Т. 2, вып. 1. — С. 115–125. — doi:10.1007/BF00149287..

Ссылки