WikiDer > Граф Бринкмана

Brinkmann graph
Граф Бринкмана
Граф Бринкмана LS.svg
Граф Бринкмана
Названный в честьГуннар Бринкманн
Вершины21
Края42
Радиус3
Диаметр3
Обхват5
Автоморфизмы14 (D7)
Хроматическое число4
Хроматический индекс5
Толщина книги3
Номер очереди2
ХарактеристикиЭйлеров
Гамильтониан
Таблица графиков и параметров

в математический поле теория графов, то Граф Бринкмана это 4-регулярный график с 21 вершиной и 42 ребрами, обнаруженными Гуннаром Бринкманном в 1992 году.[1][2] Впервые он был опубликован Бринкманном и Мерингером в 1997 году.[3]

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

К Теорема Брукса, каждый k-регулярный граф (кроме нечетных циклов и клик) имеет хроматическое число не более k. Также с 1959 года было известно, что на каждый k и л существуют k-хроматические графики с обхватом л.[5] В связи с этими двумя результатами и несколькими примерами, включая Хваталь графБранко Грюнбаум предположил в 1970 году, что для каждого k и л существуют k-хроматический k-регулярные графики с обхватом л.[6] Граф Хватала решает случай k = л = 4 этой гипотезы, и граф Бринкмана решает случай k =  4, л = 5. Гипотеза Грюнбаума была опровергнута для достаточно больших k Иогансеном, который показал, что хроматическое число граф без треугольников есть O (Δ / log Δ), где Δ - максимальная степень вершины, а O вводит нотация большой O.[7] Однако, несмотря на это опровержение, поиск примеров по-прежнему представляет интерес, и известны лишь очень немногие из них.

В хроматический полином графа Бринкмана есть Икс21 - 42Икс20 + 861Икс19 - 11480Икс18 + 111881Икс17 - 848708Икс16 + 5207711Икс15 - 26500254Икс14 + 113675219Икс13 - 415278052Икс12 + 1299042255Икс11 - 3483798283Икс10 + 7987607279Икс9 - 15547364853Икс8 + 25384350310Икс7 - 34133692383Икс6 + 36783818141Икс5 - 30480167403Икс4 + 18168142566Икс3 - 6896700738Икс2 + 1242405972Икс (последовательность A159192 в OEIS).

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

Граф Бринкмана не является вершинно-транзитивный граф и его полная группа автоморфизмов изоморфна группе группа диэдра порядка 14 группа симметрий семиугольник, включая как вращения, так и отражения.

В характеристический многочлен графа Бринкмана есть .

Галерея

Рекомендации

  1. ^ Вайсштейн, Эрик В. «Граф Бринкмана». MathWorld.
  2. ^ Бринкманн, Г. "Создание кубических графов быстрее, чем проверка изоморфизма". Препринт 92-047 SFB 343. Билефельд, Германия: Университет Билефельда, 1992.
  3. ^ а б Бринкманн Г. и Мерингер М. «Наименьшие 4-правильные 4-хроматические графы с 5 обхватом». Graph Theory Notes of New York 32, 40-41, 1997.
  4. ^ Джессика Вольц, Инженерные линейные схемы с SAT. Магистерская работа, Тюбингенский университет, 2018 г.
  5. ^ Эрдеш, Пол (1959), «Теория графов и вероятность», Канадский математический журнал, 11 (0): 34–38, Дои:10.4153 / CJM-1959-003-9.
  6. ^ Грюнбаум, Б. (1970), «Задача раскраски графа», Американский математический ежемесячный журнал, Математическая ассоциация Америки, 77 (10): 1088–1092, Дои:10.2307/2316101, JSTOR 2316101.
  7. ^ Рид, Б.А. (1998), «ω, Δ и χ», Журнал теории графов, 27 (4): 177–212, Дои:10.1002 / (SICI) 1097-0118 (199804) 27: 4 <177 :: AID-JGT1> 3.0.CO; 2-K.