Граф Татта

Граф Татта
Назван в честь	Уильям Томас Татт
Вершин	46
Рёбер	69
Радиус	5
Диаметр	8
Обхват	4
Автоморфизмы	3 (${\displaystyle \mathbb {Z} /3\mathbb {Z} }$)
Хроматическое число	3
Хроматический индекс	3
Свойства	кубический планарный полиэдральный
Медиафайлы на Викискладе

Граф Татта — пример кубического полиэдрального графа, не являющегося гамильтоновым. Таким образом, он служит контрпримером к гипотезе Тэйта, предполагавшей, что любой 3-регулярный многогранник имеет гамильтонов цикл^[1][2].

Построен Уильямом Таттом в 1946 году^[3]. Позднее найдены и другие контрпримеры, в большинстве случаев опирающиеся на теорему Гринберга.

Построение

Фрагмент Татта.

Граф Татта, состоит из трёх одинаковых кусков, так называемых фрагментов Татта. Фрагмент обладает свойством, что из трёх выходящих из него рёбер одно обязательно присутствует в гамильтоновом цикле в любом графе с таким фрагментом. «Обязательные» рёбра фрагмента подходят к центральной вершине. Поскольку любой гамильтонов цикл может использовать лишь два из них, гамильтонова цикла не существует.

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

Геометрически может быть получен из тетраэдра (каждая грань которого соответствует четырём большим граням с 9 рёбрами, три из которых находятся между парами фрагментов, а четвёртая образует внешнюю грань) путём многократного отсечения трёх его вершин.

Свойства

• Имеет 46 вершин и 69 рёбер.
• Хроматическое число графа равно 3,
• Хроматический индекс равно 3,
• обхват равен 4
• Диаметр равен 8.
• Граф является 3-связным и планарным. Значит по теореме Штайница этот граф является графом многогранника. (Число граней равно 25.)
• Группа автоморфизмов графа Татта — ${\displaystyle \mathbb {Z} /3\mathbb {Z} }$, циклическая группа третьего порядка.
• Характеристический многочлен графа:

  ${\displaystyle (x-3)(x^{15}-22x^{13}+x^{12}+184x^{11}-26x^{10}-731x^{9}+199x^{8}+1383x^{7}-576x^{6}-1061x^{5}+561x^{4}+233x^{3}-151x^{2}+4x+4)^{2}}$

  ${\displaystyle (x^{15}+3x^{14}-16x^{13}-50x^{12}+94x^{11}+310x^{10}-257x^{9}-893x^{8}+366x^{7}+1218x^{6}-347x^{5}-717x^{4}+236x^{3}+128x^{2}-56x+4)}$.

Вариации

Хотя граф Татта является исторически первым 3-регулярным негамильтоновым полиэдральным графом, он не является наименьшим из таковых.

• В 1965 году Ледерберг (Lederberg) нашёл граф с 38 вершинами (граф Барнетта — Босака — Ледерберга)^[4][5],
• В 1968 году Гринберг построил ещё несколько контрпримеров для гипотезы Тэйта — графы Гринберга с 42, 44 и 46 вершинами^[6], а в 1974 году найдены ещё два таких графа (графы Фолкнера — Янгера) с 42 и 44 вершинами^[7]. В 1988 году установлено, что существует в точности шесть негамильтоновых полиэдральных графов с 38 вершинами, имеющих нетривиальные сечения трёх рёбер, они образуются путём замены двух вершин пятиугольной призмы тем же фрагментом, что используется в примере Татта^[8].

Примечания

1. P. G. Tait. Listing's Topologie // Philosophical Magazine (5th ser.). — 1884. — Т. 17. — С. 30–46.. Статья перепечатана в Scientific Papers, Vol. II, pp. 85-98.
2. 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.
3. Weisstein, Eric W. Tutte's Graph (англ.) на сайте Wolfram MathWorld.
4. Lederberg, J. «DENDRAL-64: A System for Computer Construction, Enumeration and Notation of Organic Molecules as Tree Structures and Cyclic Graphs. Part II. Topology of Cyclic Graphs.» Interim Report to the National Aeronautics and Space Administration. Grant NsG 81-60. December 15, 1965. [1] Архивная копия от 20 мая 2014 на Wayback Machine
5. Weisstein, Eric W. Barnette-Bosák-Lederberg Graph (англ.) на сайте Wolfram MathWorld.
6. Э. Я. Гринберг. Плоские однородные графы степени три без гамильтоновых циклов. // Латв. матем. ежегодник. — Т. 4. — С. 51-58..
7. G. B. Faulkner, D. H. Younger. Non-Hamiltonian Cubic Planar Maps. // Discrete Mathematics. — 1974. — Т. 7. — С. 67-74.
8. D. A. Holton, B. D. McKay. The smallest non-Hamiltonian 3-connected cubic planar graphs have 38 vertices // Journal of Combinatorial Theory, Series B. — 1988. — Т. 45, вып. 3. — С. 305–319. — doi:10.1016/0095-8956(88)90075-5.