Gráfico de Brinkmann
| Gráfico de Brinkmann | |
|---|---|
 El gráfico de Brinkmann | |
| Lleva el nombre de | Gunnar Brinkmann |
| Vértices | 21 |
| Bordes | 42 |
| Radio | 3 |
| Diámetro | 3 |
| Circunferencia | 5 |
| Automorfismos | 14 ( D 7 ) |
| Número cromático | 4 |
| Índice cromático | 5 |
| Espesor del libro | 3 |
| Número de cola | 2 |
| Propiedades | Hamiltoniano euleriano |
| Tabla de gráficos y parámetros | |
En el campo matemático de la teoría de grafos , el grafo de Brinkmann es un grafo 4- regular con 21 vértices y 42 aristas descubierto por Gunnar Brinkmann en 1992. [1] [2] Fue publicado por primera vez por Brinkmann y Meringer en 1997. [3]
Tiene número cromático 4, índice cromático 5, radio 3, diámetro 3 y circunferencia 5. También es un gráfico conectado a 3 vértices y un gráfico conectado a 3 aristas . Es el gráfico 4-regular más pequeño de circunferencia 5 con número cromático 4. [3] Tiene un grosor de libro 3 y un número de cola 2. [4]
Según el teorema de Brooks , cada k- grafo regular (excepto los ciclos impares y las camarillas) tiene un número cromático como máximo k . También se sabía desde 1959 que, para cada k y l existen k -gráficos cromáticos con circunferencia l . [5] En relación con estos dos resultados y varios ejemplos, incluido el gráfico de Chvátal , Branko Grünbaum conjeturó en 1970 que para cada k y l existen k -cromáticos k- gráficos regulares con circunferencia l . [6] El gráfico de Chvátal resuelve el caso.k = l = 4 de esta conjetura y la gráfica de Brinkmann resuelve el caso k = 4, l = 5. La conjetura de Grünbaum fue refutada por una k suficientemente grande por Johannsen, quien demostró que el número cromático de una gráfica sin triángulos es O (Δ / log Δ) donde Δ es el grado máximo de vértice y la O introduce la notación O grande . [7] Sin embargo, a pesar de esta refutación, sigue siendo interesante encontrar ejemplos y solo se conocen muy pocos.
El polinomio cromático de la gráfica de Brinkmann es x 21 - 42 x 20 + 861 x 19 - 11480 x 18 + 111881 x 17 - 848708 x 16 + 5207711 x 15 - 26500254 x 14 + 113675219 x 13 - 415278052 x 12 + 1299042255 x 11 - 3483798283 x 10 + 7987607279 x 9 - 15547364853 x 8 + 25384350310 x 7- 34133692383 x 6 + 36783818141 x 5 - 30480167403 x 4 + 18168142566 x 3 - 6896700738 x 2 + 1242405972 x (secuencia A159192 en la OEIS ).
Propiedades algebraicas
El gráfico de Brinkmann no es un gráfico de vértice transitivo y su grupo de automorfismos completo es isomorfo al grupo diedro de orden 14, el grupo de simetrías de un heptágono , que incluye tanto rotaciones como reflexiones.
El polinomio característico del gráfico de Brinkmann es .
Galería
El número cromático del gráfico de Brinkmann es 4.
El índice cromático del gráfico de Brinkmann es 5.
Referencias
- ^ Weisstein, Eric W. "Gráfico de Brinkmann" . MathWorld .
- ^ Brinkmann, G. "Generación de gráficos cúbicos más rápido que la verificación de isomorfismo". Preprint 92-047 SFB 343. Bielefeld, Alemania: Universidad de Bielefeld, 1992.
- ^ a b Brinkmann, G. y Meringer, M. "Los gráficos 4-cromáticos 4 regulares más pequeños con circunferencia 5". Notas de teoría de grafos de Nueva York 32, 40-41, 1997.
- ^ Jessica Wolz, Diseños lineales de ingeniería con SAT . Tesis de maestría, Universidad de Tübingen, 2018
- ^ Erdős, Paul (1959), "Teoría de grafos y probabilidad", Canadian Journal of Mathematics , 11 : 34–38, doi : 10.4153 / CJM-1959-003-9.
- ^ Grünbaum, B. (1970), "Un problema en la coloración de gráficos", American Mathematical Monthly , Asociación Matemática de América, 77 (10): 1088-1092, doi : 10.2307 / 2316101 , JSTOR 2316101 .
- ^ Reed, BA (1998), "ω, Δ y χ", Journal of Graph Theory , 27 (4): 177-212, doi : 10.1002 / (SICI) 1097-0118 (199804) 27: 4 <177: : AID-JGT1> 3.0.CO; 2-K.
- Gráficos individuales
- Gráficos regulares
