Граф Титце

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

В теории графов граф Титце — это неориентированный кубический граф с 12 вершинами и 18 рёбрами. Граф назван именем Генриха Титце, показавшего в 1910 году, что ленту Мёбиуса можно разделить на шесть областей, касающихся друг друга — три вдоль границы ленты и три вдоль центральной линии — а потому для графов, допускающих вложение в ленту Мёбиуса, может потребоваться шесть цветов[1]. Граничные сегменты областей Титца разделения ленты Мёбиуса (включая сегменты вдоль границы самой ленты) образуют вложение графа Титце.

Связь с графом Петерсена

Граф Титце можно получить из графа Петерсена заменой одной из его вершин треугольником[2]. Подобно графу Титце граф Петерсена служит границами шести взаимно соприкасающихся областей, но в проективной плоскости, а не на ленте Мёбиуса. Если вырезать окрестность некоторой вершины этого разбиения проективной плоскости, вершина заменяется границами этой дыры, что даёт в точности построение графа Титце, описанное выше.

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

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

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

Рёберная раскраска и совершенные паросочетания

Рёберная раскраска графа Титце требует четырёх цветов, то есть его хроматический индекс равен 4. Это эквивалентно тому, что рёбра графа Титца могут быть разделены на четыре паросочетания, но не меньше.

Граф Титце удовлетворяет части требований определения снарка — он является кубическим графом без мостов и его рёбра не могут быть выкрашены в 3 цвета. Однако некоторые авторы ограничивают снарки графами без 3-циклов и 4-циклов, а при этих более сильных условиях граф Титце не является снарком. Граф Титце изоморфен графу J3, графу из бесконечного семейства снарков «Цветок», предложенных Р. Исаакксом в 1975 году[4].

В отличие от графа Петерсена, граф Титце может быть покрыт четырьмя совершенными паросочетаниями. Это свойство играет ключевую роль в доказательстве, что проверка, можно ли покрыть граф четырьмя совершенными паросочетаниями, является NP-полной задачей[5].

Дополнительные свойства

Граф Титце имеет хроматическое число 3, хроматический индекс 4, обхват 3 и диаметр 3. Его число независимости равно 5, а группа автоморфизмов имеет порядок 12 и она изоморфна диэдрической группе D6, группе симметрий шестиугольника, включающей как вращения, так и отражения. Эта группа содержит две орбиты размера 3 и одну размера 6 на вершинах, а потому этот граф не вершинно транзитивен.

Галерея

См. также

Примечания

  1. ↑ Tietze, 1910, с. 155-159.
  2. ↑ 1 2 Clark, Entringer, 1983, с. 57–68.
  3. ↑ Punnim, Saenpholphat, Thaithae, 2007, с. 83–86.
  4. ↑ Isaacs, 1975, с. 221–239.
  5. ↑ Esperet, Mazzuoccolo, 2014, с. 144–157.

Литература

  • L. Clark, R. Entringer. Smallest maximally nonhamiltonian graphs // Periodica Mathematica Hungarica. — 1983. — Т. 14, вып. 1. — doi:10.1007/BF02023582.
  • Narong Punnim, Varaporn Saenpholphat, Sermsri Thaithae. Almost Hamiltonian cubic graphs // International Journal of Computer Science and Network Security. — 2007. — Т. 7, вып. 1.
  • R. Isaacs. Infinite families of nontrivial trivalent graphs which are not Tait colorable // Amer. Math. Monthly. — Mathematical Association of America, 1975. — Т. 82, вып. 3. — doi:10.2307/2319844. — JSTOR 2319844.
  • Heinrich Tietze. Einige Bemerkungen zum Problem des Kartenfärbens auf einseitigen Flächen (Some remarks on the problem of map coloring on one-sided surfaces) // DMV Annual Report. — 1910. — Т. 19. (недоступная ссылка)
  • L. Clark, R. Entringer. Smallest maximally nonhamiltonian graphs // Periodica Mathematica Hungarica. — 1983. — Т. 14, вып. 1. — doi:10.1007/BF02023582.
  • L. Esperet, G. Mazzuoccolo. On cubic bridgeless graphs whose edge-set cannot be covered by four perfect matchings // Journal of Graph Theory. — 2014. — Т. 77, вып. 2. — doi:10.1002/jgt.21778. — arXiv:1301.6926.