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