График Гольднера – Харари - Goldner–Harary graph

График Гольднера – Харари
Гольднер-Харари graph.svg
Названный в честьА. Гольднер,
Фрэнк Харари
Вершины11
Края27
Радиус2
Диаметр2
Обхват3
Автоморфизмы12 (D6)
Хроматическое число4
Хроматический индекс8
ХарактеристикиМногогранник
Планарный
Хордовый
Идеально
Ширина дерева  3
Таблица графиков и параметров

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

Характеристики

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

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

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

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

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

Геометрия

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

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

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

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

В характеристический многочлен графа Гольднера – Харари: .

Рекомендации

  1. ^ Goldner, A .; Харари, Ф. (1975), "Замечание о наименьшем негамильтоновом максимальном плоском графе", Бык. Malaysian Math. Soc., 6 (1): 41–42. См. Также тот же журнал 6(2): 33 (1975) и 8: 104-106 (1977). Ссылка из список публикаций Харари.
  2. ^ Дилленкур, М. Б. (1996), "Многогранники малых порядков и их гамильтоновы свойства", Журнал комбинаторной теории, серия B, 66: 87–122, Дои:10.1006 / jctb.1996.0008.
  3. ^ Читать, R.C .; Уилсон, Р. Дж. (1998), Атлас графиков, Оксфорд, Англия: Издательство Оксфордского университета, стр. 285.
  4. ^ а б Грюнбаум, Бранко (1967), Выпуклые многогранники, Wiley Interscience, стр. 357. Та же страница, 2-е изд., Тексты для выпускников по математике 221, Springer-Verlag, 2003, ISBN  978-0-387-40409-7.
  5. ^ Bernhart, Frank R .; Кайнен, Пол К. (1979), «Книжная толщина графа», Журнал комбинаторной теории, Серия B, 27 (3): 320–331, Дои:10.1016/0095-8956(79)90021-2. См., В частности, рисунок 9.
  6. ^ Яннакакис, Михалис (1986), «Четыре страницы необходимы и достаточно для плоских графов», Proc. 18-й симпозиум ACM. Теория вычислений (STOC), стр. 104–108, Дои:10.1145/12130.12141.
  7. ^ Эвальд, Гюнтер (1973), "Гамильтоновы схемы в симплициальных комплексах", Geometriae Dedicata, 2 (1): 115–125, Дои:10.1007 / BF00149287.

внешняя ссылка