Граф Хершеля

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

В теории графов граф Хершеля — это двудольный неориентированный граф с 11 вершинами и 18 рёбрами, наименьший негамильтонов полиэдральный граф. Граф назван по имени британского астронома А. С. Хершеля, написавшего раннюю работу по поводу игры «Икосиан» Уильяма Роуэна Гамильтона — граф Хершеля даёт наименьший выпуклый многогранник, для которого игра не имеет решения. Однако статья Хершеля описывает решения для игры «Икосиан» только для тетраэдра и икосаэдра, и не описывает граф Хершеля.

Свойства

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

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

Гамильтоновость

Поскольку граф является двудольным и имеет нечётное число вершин, он не содержит гамильтонов цикл (цикл из рёбер, который проходит через каждую вершину в точности один раз). В любом двудольном графе любой цикл должен попеременно проходить оба множества вершин, а потому, должен содержать равное число вершин обоих типов и иметь чётную длину. Таким образом, цикл, проходящий через каждую из одиннадцати вершин, существовать не может. Граф является минимальным негамильтоновым полиэдральным графом, как бы ни измерялся размер графа — по числу вершин, рёбер или граней. Существует другой полиэдральный граф с 11 вершинами, не имеющий гамильтоновых циклов (а именно, граф Голднера — Харари), но нет графа с меньшим (либо равным) числом рёбер.

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

Граф Хершеля даёт также пример полиэдрального графа, для которого срединный граф не может быть разбит на два непересекающихся по рёбрам гамильтонова цикла. Серединным графом графа Хершеля является 4-регулярный граф с 18 вершинами, по одной для каждого ребра графа Хершеля. Две вершины смежны в срединном графе, если соответствующие рёбра графа Хершеля идут последовательно на одной из его граней.

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

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

Характеристический многочлен графа Хершеля равен $-x^{3}(x^{2}-11)(x^{2}-3)(x^{2}-2)^{2}$.

Ссылки

• Weisstein, Eric W. Herschel Graph (англ.) на сайте Wolfram MathWorld.