En el campo matemático de la teoría de grafos , el grafo de Brouwer-Haemers es un grafo no dirigido regular de 20 con 81 vértices y 810 aristas. Es un gráfico fuertemente regular , un gráfico transitivo a distancia y un gráfico Ramanujan . Aunque su construcción es folclórica, recibió su nombre de Andries Brouwer y Willem H. Haemers, quienes demostraron su singularidad como gráfico fuertemente regular.
Gráfico de Brouwer-Haemers | |
---|---|
Vértices | 81 |
Bordes | 810 |
Radio | 2 |
Diámetro | 2 |
Circunferencia | 3 |
Automorfismos | 233,280 |
Número cromático | 7 |
Propiedades | |
Tabla de gráficos y parámetros |
Construcción
El gráfico de Brouwer-Haemers tiene varias construcciones algebraicas relacionadas. Uno de los más simples es un gráfico de Paley generalizado de grado 4 : se puede definir haciendo un vértice para cada elemento en el campo finito y una ventaja por cada dos elementos que difieran en una cuarta potencia . [1] [2]
Propiedades
El gráfico de Brouwer-Haemers es el único gráfico fuertemente regular con parámetros (81, 20, 1, 6). Esto significa que tiene 81 vértices, 20 aristas por vértice, 1 triángulo por arista y 6 recorridos de dos longitudes que conectan cada par de vértices no adyacentes. [3] Como un gráfico fuertemente regular con el tercer parámetro igual a 1, el gráfico de Brouwer-Haemers tiene la propiedad de que cada borde pertenece a un triángulo único; es decir, es localmente lineal . Encontrar gráficos grandes y densos con esta propiedad es una de las formulaciones del problema de Ruzsa-Szemerédi . [4]
Además de ser muy regular, es un gráfico transitivo a la distancia . [5]
Historia
Aunque Brouwer escribe que la "construcción es folklore" de este gráfico, y cita como referencia temprana un artículo de 1964 sobre cuadrados latinos de Dale M. Mesner, [1] lleva el nombre de Andries Brouwer y Willem H. Haemers, quienes en 1992 publicaron un prueba de que es el único gráfico fuertemente regular con los mismos parámetros. [3]
Gráficos relacionados
El gráfico de Brouwer-Haemers es el primero de una familia infinita de gráficos de Ramanujan definidos como gráficos de Paley generalizados sobre campos de característica tres. [2] Con el El gráfico de Rook y el gráfico de Juegos , es uno de los tres posibles gráficos fuertemente regulares cuyos parámetros tienen la forma. [6]
Debe distinguirse del gráfico Sudoku , un gráfico diferente de 81 vértices regulares de 20. El gráfico de Sudoku se deriva de los rompecabezas de Sudoku haciendo un vértice para cada cuadrado del rompecabezas y conectando dos cuadrados por un borde cuando pertenecen a la misma fila, columna obloque del rompecabezas. Tiene muchas camarillas de 9 vértices y requiere 9 colores en cualquier color de gráfico ; un color de 9 de este gráfico describe un Sudoku resuelto. [7] [8] En contraste, para el gráfico de Brouwer-Haemers, los grupos más grandes son los triángulos y la cantidad de colores necesarios es 7. [5]
Referencias
- ^ a b Brouwer, Andries , "Gráfico de Brouwer-Haemers" , Descripciones de varios gráficos , consultado el 11 de febrero de 2019
- ^ a b Podestá, Ricardo A .; Videla, Denis E. (2018), Los espectros de gráficos y aplicaciones de Paley generalizados , arXiv : 1812.03332
- ^ a b Brouwer, AE ; Haemers, WH (1992), "Estructura y singularidad del gráfico fuertemente regular (81,20,1,6)", una colección de contribuciones en honor a Jack van Lint, Discrete Mathematics , 106/107: 77-82, doi : 10.1016 / 0012-365X (92) 90532-K , Señor 1181899
- ^ Clark, LH; Entringer, RC; McCanna, JE; Székely, LA (1991), "Problemas extremos para las propiedades locales de los gráficos" (PDF) , The Australasian Journal of Combinatorics , 4 : 25–31, MR 1129266
- ^ a b Weisstein, Eric W. "Gráfico de Brouwer-Haemers" . MathWorld .
- ^ Bondarenko, Andriy V .; Radchenko, Danylo V. (2013), "En una familia de gráficos fuertemente regulares con", Journal of Combinatorial Theory , Serie B, 103 (4): 521–531, arXiv : 1201.0383 , doi : 10.1016 / j.jctb.2013.05.005 , MR 3071380
- ^ Gago-Vargas, Jesús; Hartillo-Hermoso, María Isabel; Martín-Morales, Jorge; Ucha-Enríquez, Jose Maria (2006), "Bases Sudokus y Gröbner: No solo un divertimento ", en Ganzha, Victor G .; Mayr, Ernst W .; Vorozhtsov, Evgenii V. (eds.), Computer Algebra in Scientific Computing, 9th International Workshop, CASC 2006, Chisinau, Moldova, 11-15 de septiembre de 2006, Actas , Lecture Notes in Computer Science, 4194 , Springer, págs. 155– 165, doi : 10.1007 / 11870814_13
- ^ Herzberg, Agnes M .; Murty, M. Ram (2007), "Cuadrados de Sudoku y polinomios cromáticos" (PDF) , Notices of the American Mathematical Society , 54 (6): 708–717, MR 2327972