В математической области теории графов , граф Титце является неориентированный кубический граф с 12 вершинами и 18 ребрами. Он назван в честь Генриха Франца Фридриха Титце , который в 1910 году показал, что ленту Мебиуса можно разделить на шесть областей, которые все соприкасаются друг с другом - три вдоль границы полосы и три вдоль ее центральной линии - и, следовательно, эти графы, которые встроены на ленту Мебиуса может потребоваться шесть цветов . [1] Граничные сегменты областей подразделения Титце (включая сегменты вдоль границы самой ленты Мёбиуса) образуют вложение графа Титце.
График Титце | |
---|---|
Вершины | 12 |
Края | 18 |
Радиус | 3 |
Диаметр | 3 |
Обхват | 3 |
Автоморфизмы | 12 ( пр. 6 ) |
Хроматическое число | 3 |
Хроматический индекс | 4 |
Характеристики | Кубический Снарк |
Таблица графиков и параметров |
Связь с графом Петерсена
Граф Титце может быть образован из графа Петерсена путем замены одной из его вершин треугольником . [2] [3] Подобно графу Титце, граф Петерсена образует границу шести взаимно соприкасающихся областей, но на проективной плоскости, а не на ленте Мёбиуса. Если вырезать отверстие из этого подразделения проективной плоскости, окружающего единственную вершину, окруженная вершина заменяется треугольником границ области вокруг отверстия, что дает ранее описанную конструкцию графа Титце.
Гамильтоничность
И граф Титце, и граф Петерсена максимально негамильтоновы : у них нет гамильтонова цикла , но любые две несмежные вершины могут быть соединены гамильтоновым путем. [2] Граф Титце и граф Петерсена - единственные кубические негамильтоновы графы с 2-вершинной связью, содержащие 12 или меньше вершин. [4]
В отличие от графа Петерсена, граф Титце не является гипогамильтоновым : удаление одной из трех вершин треугольника образует меньший граф, который остается негамильтоновым.
Раскраска кромок и идеальное соответствие
Для раскраски ребер графа Титце требуется четыре цвета; то есть его хроматический индекс равен 4. Точно так же ребра графа Титце можно разделить на четыре сопоставления , но не меньше.
Граф Титце частично соответствует определению снарка : это кубический граф без мостов, который нельзя раскрашивать по 3 ребрам . Однако некоторые авторы ограничивают снарки графами без 3-циклов и 4-циклов, и в соответствии с этим более ограничительным определением граф Титце не является снарком. Граф Титце изоморфен графу J 3 , части бесконечного семейства цветочных снарков, введенного Р. Айзексом в 1975 г. [5]
В отличие от графа Петерсена, граф Титце может быть покрыт четырьмя точными сопоставлениями . Это свойство играет ключевую роль в доказательстве того, что проверка того, может ли граф покрыться четырьмя точными сопоставлениями, является NP-полной . [6]
Дополнительные свойства
Граф Титце имеет хроматическое число 3, хроматический индекс 4, обхват 3 и диаметр 3. Число независимости равно 5. Его группа автоморфизмов имеет порядок 12 и изоморфна группе диэдра D 6 , группе симметрий шестиугольника , включая обе группы. вращения и отражения. Эта группа имеет две орбиты размера 3 и одну размера 6 на вершинах, поэтому этот граф не является вершинно-транзитивным .
Галерея
Хроматическое число графа Титс равно 3.
Хроматической индекс графа Титс равен 4.
Граф Титце имеет перекресток номер 2 и является 1-плоским .
Смотрите также
- Дюрер график и Франклина график , два других 12-вершинные графы кубических
Заметки
- ^ Титце, Генрих (1910), "Einige Bemerkungen zum Problem des Kartenfärbens auf einseitigen Flächen" [Некоторые замечания по проблеме раскраски карты на односторонних поверхностях], Годовой отчет DMV , 19 : 155–159[ постоянная мертвая ссылка ] .
- ^ а б Clark, L .; Энтрингер Р. (1983), "Наименьшие максимально негамильтоновы графы", Periodica Mathematica Hungarica , 14 (1): 57–68, DOI : 10.1007 / BF02023582
- ^ Вайсштейн, Эрик В. "График Титце" . MathWorld .
- ^ Пунним, Наронг; Саенфольфат, Варапорн; Тайта, Сермсри (2007), «Почти гамильтоновы кубические графы» (PDF) , Международный журнал компьютерных наук и сетевой безопасности , 7 (1): 83–86
- ^ Айзекс, Р. (1975), "Бесконечные семейства нетривиальных трехвалентных графов, которые не раскрашиваются по Тейту", Amer. Математика. Ежемесячно , Математическая ассоциация Америки, 82 (3): 221-239, DOI : 10,2307 / 2319844 , JSTOR 2319844.
- ^ Esperet, L .; Маццуокколо, Г. (2014), «О кубических графах без мостов, набор ребер которых не может быть покрыт четырьмя точными сопоставлениями», Журнал теории графов , 77 (2): 144–157, arXiv : 1301.6926 , doi : 10.1002 / jgt. 21778 , MR 3246172.