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

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

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

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

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

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

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

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

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

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

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

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

Галерея

• 
  Хроматическое число графа Титце равно 3.
• 
  Хроматический индекс графа Титца равен 4.
• 
  Граф Титце имеет число пересечений 2 и он 1-планарен .
• 
  Трёхмерное вложение графа Титце.

См. также

• Граф Дюрера и граф Франклина , два других кубических графа с 12 вершинами.

Примечания

Литература

• L. Clark, R. Entringer. Smallest maximally nonhamiltonian graphs // Periodica Mathematica Hungarica. — 1983. — Т. 14 , вып. 1 . — doi : .
• 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 : . — JSTOR .
• 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) // Annual Report. — 1910. — Т. 19 . (недоступная ссылка)
• L. Clark, R. Entringer. Smallest maximally nonhamiltonian graphs // Periodica Mathematica Hungarica. — 1983. — Т. 14 , вып. 1 . — doi : .
• 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 : . — arXiv : .