График Франклина - Википедия - Franklin graph

График Франклина
Граф Франклина hamiltonian.svg
График Франклина
Названный в честьФилип Франклин
Вершины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. ^ Вайсштейн, Эрик В. "График Франклина". MathWorld.
  2. ^ Вайсштейн, Эрик В. "Гипотеза Хивуда". MathWorld.
  3. ^ Франклин П. «Задача шести цветов». J. Math. Phys. 13, 363-379, 1934. HDL:2027 / mdp.39015019892200