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