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

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

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

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

Хроматический полином графа Бринкмана равен x ²¹ - 42 x ²⁰ + 861 x ¹⁹ - 11480 x ¹⁸ + 111881 x ¹⁷ - 848708 x ¹⁶ + 5207711 x ¹⁵ - 26500254 x ¹⁴ + 113675219 x ¹³ - 415278052 x ¹² + 1299042255 x ¹¹ - 3483798283 x ¹⁰ + 7987607279 x ⁹ - 15547364853 x ⁸ + 25384350310 x ⁷ - 34133692383 x ⁶ + 36783818141 x ⁵ - 30480167403 x ⁴ + 18168142566 x ³ - 6896700738 x ² + 1242405972 x (последовательность A159192 в OEIS ).

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

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

Характеристический многочлен графа Бринкмана равен . ${\displaystyle (x-4)(x-2)(x+2)(x^{3}-x^{2}-2x+1)^{2}}$ ${\displaystyle (x^{6}+3x^{5}-8x^{4}-21x^{3}+27x^{2}+38x-41)^{2}}$

Галерея

• 
  Альтернативный рисунок графика Бринкмана.
• 
  Хроматическое число графа Бринкмана равно 4.
• 
  Хроматический индекс графа Бринкмана равен 5.

Ссылки

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

Внешние ссылки

• Вайсштейн, Эрик В. «График Бринкмана». Математический мир .