Граф Франклина

Перейти к навигацииПерейти к поиску
Граф Франклина
Назван в честьФилип Франклин[англ.]
Вершин 12
Рёбер 18
Радиус 3
Диаметр 3
Обхват 4
Автоморфизмы 48 (Z/2Z×S4)
Хроматическое число 2
Хроматический индекс 3
Род 1
СвойстваКубический
Гамильтонов
Двудольный
Без треугольников
Совершенный
Вершинно-транзитивный
Логотип Викисклада Медиафайлы на Викискладе

В теории графов граф Франклина — это 3-регулярный граф с 12 вершинами и 18 рёбрами[1].

Граф назван именем Филипа Франклина[англ.], опровергшего гипотезу Хивуда о числе цветов, необходимых для раскраски двумерных поверхностей, разделённых на ячейки при вложении графа[2][3]. Согласно гипотезе Хивуда максимальное хроматическое число карты на бутылке Клейна должно равняться семи, однако Франклин доказал, что для данного графа шести цветов всегда достаточно. Граф Франклина может быть вложен в бутылку Клейна так, что он образует карту, требующую шесть цветов, что показывает, что в некоторых случаях шести цветов достаточно. Это вложение является Петри двойственным вложения в проективную плоскость (вложение показано ниже).

Граф является гамильтоновым и имеет хроматическое число 2, хроматический индекс 3, радиус 3, диаметр 3 и обхват 4. Он является также вершинно 3-связным и рёберно 3-связным совершенным графом.

Алгебраические свойства

Группа автоморфизмов графа Франклина имеет порядок 48 и изоморфна Z/2Z×S4, прямому произведению циклической группы Z/2Z и симметрической группы S4. Группа действует транзитивно на вершинах графа.

Характеристический многочлен графа Франклина равен

Галерея

Примечания

  1. Weisstein, Eric W. Franklin Graph (англ.) на сайте Wolfram MathWorld.
  2. Weisstein, Eric W. Heawood conjecture (англ.) на сайте Wolfram MathWorld.
  3. Franklin, 1934, с. 363-379.

Литература

  • P. Franklin. A Six Color Problem // J. Math. Phys.. — 1934. — Т. 13. — С. 363-379.