В математической области теории графов , то граф Франклина является 3- регулярного графа с 12 вершинами и 18 ребрами.
График Франклина | |
---|---|
Названный в честь | Филип Франклин |
Вершины | 12 |
Края | 18 |
Радиус | 3 |
Диаметр | 3 |
Обхват | 4 |
Автоморфизмы | 48 ( Z / 2 Z × S 4 ) |
Хроматическое число | 2 |
Хроматический индекс | 3 |
Род | 1 |
Характеристики | Кубический гамильтонова Двудольные треугольник бесплатно Идеальный Vertex-транзитивным |
Таблица графиков и параметров |
Граф Франклина назван в честь Филипа Франклина , который опроверг гипотезу Хивуда о количестве цветов, необходимых при разбиении двумерной поверхности на ячейки с помощью вложения графа . [1] Гипотеза Хивуда подразумевала, что максимальное хроматическое число карты на бутылке Клейна должно быть семь, но Франклин доказал, что в этом случае шести цветов всегда достаточно. (Бутылка Клейна - единственная поверхность, для которой гипотеза Хивуда не работает.) Граф Франклина может быть встроен в бутылку Клейна, так что он формирует карту, требующую шести цветов, показывая, что в этом случае иногда необходимы шесть цветов. Это вложение является двойственным по Петри к его вложению впроективная плоскость, показанная ниже.
Он является гамильтоновым и имеет хроматическое число 2, хроматический индекс 3, радиус 3, диаметр 3 и обхват 4. Это также идеальный граф с 3- вершинно-связными и 3- реберно связными .
Алгебраические свойства
Группа автоморфизмов графа Франклина имеет порядок 48 и изоморфна Z / 2 Z × š 4 , в прямое произведение из циклической группы Z / 2 Z а симметричная группа S 4 . Он действует транзитивно на вершинах графа, делая его вершинно-транзитивным .
Характеристический полином графа Франклин
Галерея
Хроматическим числом графа Франклина 2.
Хроматической индекс графа Франклина равен 3.
Альтернативный рисунок графа Франклина.
Граф Франклина, вложенный в проективную плоскость как усеченный полуоктаэдр .
Рекомендации
- ^ Франклин, П. «Проблема шести цветов». J. Math. Phys. 13, 363–379, 1934. hdl : 2027 / mdp.39015019892200