В математической области теории графов , то граф Бринкман является 4- регулярного графа с 21 вершинами и 42 ребрами обнаружили Гуннар Brinkmann в 1992 году [1] [2] Он был впервые опубликован Brinkmann и Meringer в 1997 году [3]
Граф Бринкмана | |
---|---|
Названный в честь | Гуннар Бринкманн |
Вершины | 21 год |
Края | 42 |
Радиус | 3 |
Диаметр | 3 |
Обхват | 5 |
Автоморфизмы | 14 ( D 7 ) |
Хроматическое число | 4 |
Хроматический индекс | 5 |
Толщина книги | 3 |
Номер очереди | 2 |
Характеристики | Эйлеров гамильтониан |
Таблица графиков и параметров |
Он имеет хроматическое число 4, хроматический индекс 5, радиус 3, диаметр 3 и обхват 5. Это также граф с 3 связями по вершинам и граф с 3 связями по ребрам . Это наименьший 4-регулярный граф обхвата 5 с хроматическим числом 4. [3] Он имеет книжную толщину 3 и номер очереди 2. [4]
По теореме Брукса каждый k -регулярный граф (кроме нечетных циклов и клик) имеет хроматическое число не более k . С 1959 года также было известно, что для любых k и l существуют k -хроматические графы с обхватом l . [5] В связи с этими двумя результатами и несколькими примерами, включая граф Хватала , Бранко Грюнбаум в 1970 году предположил, что для любых k и l существуют k -хроматические k -регулярные графы с обхватом l . [6] Граф Хватала решает случай k = l = 4 этой гипотезы, а граф Бринкмана решает случай k = 4, l = 5. Гипотеза Грюнбаума была опровергнута для достаточно больших k Иогансеном, который показал, что хроматическое число граф без треугольников представляет собой о (Δ / Δ лог) где Δ представляет максимальную степень вершины и вводит O большое обозначение O . [7] Однако, несмотря на это опровержение, поиск примеров по-прежнему представляет интерес, и известны лишь очень немногие из них.
Хроматической многочлен графа Brinkmann является й 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, группе симметрий семиугольника , включая как вращения, так и отражения.
Характеристический полином графа Brinkmann является.
Галерея
Хроматического числа графа Brinkmann равно 4.
Хроматической индекс графа Brinkmann 5.
Рекомендации
- ^ Вайсштейн, Эрик В. "Граф Бринкмана" . MathWorld .
- ^ Бринкманн, Г. "Создание кубических графов быстрее, чем проверка изоморфизма". Препринт 92-047 SFB 343. Билефельд, Германия: Университет Билефельда, 1992.
- ^ a b Бринкманн, Г. и Мерингер, М. «Наименьшие 4-правильные 4-хроматические графы с 5 обхватом». Graph Theory Notes of New York 32, 40-41, 1997.
- ^ Джессика Wolz, Инженерная Линейные Макеты с SAT . Магистерская работа, Тюбингенский университет, 2018 г.
- ^ Erdős, Пол (1959), "Теория графов и вероятность", Canadian Journal математики , 11 (0): 34-38, DOI : 10,4153 / CJM-1959-003-9.
- ^ Грюнбаум, Б. (1970), "Проблема в графике раскраски", American Mathematical Monthly , Математическая ассоциация Америки, 77 (10): 1088-1092, DOI : 10,2307 / 2316101 , JSTOR 2316101.
- ^ Рид, BA (1998), «ω, Δ и χ», Журнал теории графов , 27 (4): 177–212, DOI : 10.1002 / (SICI) 1097-0118 (199804) 27: 4 <177 :: AID-JGT1> 3.0.CO; 2-K.