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

Граф Франклина
Назван в честь Филип Франклин[англ.]
Вершин 12
Рёбер 18
Радиус 3
Диаметр 3
Обхват 4
Автоморфизмы 48 (Z/2Z×S4)
Хроматическое число 2
Хроматический индекс 3
Род 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.