Граф Татта

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

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

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

Построение

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

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

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

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

Свойства

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

  $(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}$

  $(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 вершинами (граф Барнетта — Босака — Ледерберга),
• В 1968 году Гринберг построил ещё несколько контрпримеров для гипотезы Тэйта — графы Гринберга с 42, 44 и 46 вершинами, а в 1974 году найдены ещё два таких графа (графы Фолкнера — Янгера) с 42 и 44 вершинами. В 1988 году установлено, что существует в точности шесть негамильтоновых полиэдральных графов с 38 вершинами, имеющих нетривиальные сечения трёх рёбер, они образуются путём замены двух вершин пятиугольной призмы тем же фрагментом, что используется в примере Татта.