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