Граф Гершеля

У теорії графів граф Гершеля — двочастковий неорієнтований граф із 11 вершинами і 18 ребрами, найменший негамільтонів поліедральний граф. Граф названо на честь британського астронома ^[en], який написав ранню роботу з приводу гри «Ікосіан» Вільяма Ровена Гамільтона — граф Гершеля дає найменший опуклий многогранник, для якого гра не має розв'язку. Однак стаття Гершеля описує розв'язок для гри «Ікосіан» тільки для тетраедра та ікосаедра, і не описує графа Гершеля.

Властивості

Граф Гершеля планарний — його можна намалювати на площині без перехрещення ребер. Він також 3-вершинно-зв'язний — видалення будь-яких двох вершин залишає підграф зв'язним. Тому, за теоремою Штайніца, граф Гершеля є багатогранним графом — існує опуклий многогранник (еннеаедр), для якого він є скелетом. Граф Гершеля є також двочастковим — його вершини можна розбити на дві підмножини з п'яти і шести вершин так, що кожне ребро матиме кінцеві вершини в обох множинах (червоні та сині підмножини на малюнку).

Як і будь-який інший двочасковий граф, граф Гершеля є досконалим — хроматичне число будь-якого породженого підграфа дорівнює розміру найбільшої кліки цього підграфа. Граф має хроматичний індекс 4, обхват 4, радіус 3 та діаметр 4.

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

Оскільки граф двочастковий і має непарне число вершин, він не містить гамільтонового циклу (циклу з ребер, який проходить через кожну вершину рівно один раз). У будь-якому двочастковому графі будь-який цикл має поперемінно проходити обидві множини вершин, тому повинен містити однакову кількість вершин обох типів і мати парну довжину. Таким чином, цикл, що проходить через кожну з одинадцяти вершин, не може існувати. Граф є мінімальним негамільтоновим багатогранним графом, хоч би як вимірювався розмір графа — за кількістю вершин, ребер чи граней. Існує інший багатограний граф з 11 вершинами, що не має гамільтонових циклів (а саме, граф Голднера — Харарі), але немає графа з меншим (або рівним) числом ребер.

Усі вершини графа Гершеля, крім трьох, мають степінь три. Гіпотеза Тета стверджує, що багатогранний граф, у якому будь-яка вершина має степінь три, має бути гамільтоновим, але її спростував Татт, навівши контрприклад — значно більший граф Татта. Оновлення гіпотези Тета, гіпотеза Барнетте, що будь-який двочастковий 3-регулярний багатогранний граф є гамільтоновим, залишається відкритою.

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

Алгебричні властивості

Граф Гершеля не вершинно-транзитивний і його повна група автоморфізмів ізоморфна діедральній групі 12 порядку, групі симетрій правильного шестикутника, що включає як обертання, так і відбиття. Будь-яку перестановку його вершин степеня 4 можна подати автоморфізмом графа, і існує ще нетривіальний автоморфізм, що переставляє решту вершин, не зачіпаючи вершин степеня 4.

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

Примітки

1. A. S. Herschel. Sir Wm. Hamilton's Icosian Game // . — 1862. — Т. 5. — С. 305.
2. H. S. M. Coxeter. . — Dover, 1973. — С. 8.
3. David Barnette, Ernest Jucovič. Hamiltonian circuits on 3-polytopes // Journal of Combinatorial Theory. — 1970. — Т. 9, вип. 1. — С. 54—59. — DOI:10.1016/S0021-9800(70)80054-0.
4. P. G. Tait. Listing's Topologie // Philosophical Magazine (5th ser.). — 1884. — Т. 17. — С. 30—46.. Перепечатано в Scientific Papers, Vol. II, стр. 85—98.
5. W. T. Tutte. On Hamiltonian circuits // Journal of the London Mathematical Society. — 1946. — Т. 21, вип. 2. — С. 98—101. — DOI:10.1112/jlms/s1-21.2.98.
6. Robert Samal. Barnette's conjecture. — the Open Problem Garden, 11 June 2007.
7. J. A. Bondy, R. Häggkvist. Edge-disjoint Hamilton cycles in 4-regular planar graphs // Aequationes Mathematicae. — 1981. — Т. 22, вип. 1. — С. 42—45. — DOI:10.1007/BF02190157.

Посилання

• Weisstein, Eric W. Граф Гершеля(англ.) на сайті Wolfram MathWorld.