En el campo matemático de la teoría de grafos , el grafo de Heawood es un grafo no dirigido con 14 vértices y 21 aristas, que lleva el nombre de Percy John Heawood . [1]
| Gráfico Heawood | |
|---|---|
 | |
| Lleva el nombre de | Percy John Heawood |
| Vértices | 14 |
| Bordes | 21 |
| Radio | 3 |
| Diámetro | 3 |
| Circunferencia | 6 |
| Automorfismos | 336 ( PGL 2 (7) ) |
| Número cromático | 2 |
| Índice cromático | 3 |
| Género | 1 |
| Espesor del libro | 3 |
| Número de cola | 2 |
| Propiedades | Jaula cúbica bipartita Distancia transitiva Distancia regular Toroidal Hamiltoniano Simétrico Orientablemente simple |
| Tabla de gráficos y parámetros | |
Propiedades combinatorias
El gráfico es cúbico y todos los ciclos del gráfico tienen seis o más aristas. Cada gráfico cúbico más pequeño tiene ciclos más cortos, por lo que este gráfico es el gráfico de 6 cajas , el gráfico cúbico más pequeño de circunferencia 6. Es un gráfico de distancia transitiva (ver el censo de Foster ) y, por lo tanto, la distancia regular . [2]
Hay 24 coincidencias perfectas en el gráfico de Heawood; para cada emparejamiento, el conjunto de aristas que no están en el emparejamiento forma un ciclo hamiltoniano . Por ejemplo, la figura muestra los vértices del gráfico colocados en un ciclo, con las diagonales internas del ciclo formando una coincidencia. Al subdividir los bordes del ciclo en dos coincidencias, podemos dividir el gráfico de Heawood en tres coincidencias perfectas (es decir, 3 colores de sus bordes ) de ocho formas diferentes. [2] Cada dos emparejamientos perfectos y cada dos ciclos hamiltonianos se pueden transformar entre sí mediante una simetría del gráfico. [3]
Hay 28 ciclos de seis vértices en el gráfico de Heawood. Cada 6 ciclos es distinto de exactamente otros 6 ciclos; entre estos tres 6 ciclos, cada uno es la diferencia simétrica de los otros dos. El gráfico con un nodo por cada 6 ciclos y un borde por cada par disjunto de 6 ciclos es el gráfico de Coxeter . [4]
Propiedades geométricas y topológicas
El gráfico de Heawood es un gráfico toroidal ; es decir, se puede incrustar sin cruces en un toro . Una incrustación de este tipo coloca sus vértices y aristas en el espacio euclidiano tridimensional como el conjunto de vértices y aristas de un poliedro no convexo con la topología de un toro, el poliedro de Szilassi .
El gráfico lleva el nombre de Percy John Heawood , quien en 1890 demostró que en cada subdivisión del toro en polígonos, las regiones poligonales se pueden colorear con un máximo de siete colores. [5] [6] El gráfico de Heawood forma una subdivisión del toro con siete regiones adyacentes entre sí, lo que muestra que este límite es estrecho.
El gráfico de Heawood es el gráfico de Levi del plano de Fano , el gráfico que representa las incidencias entre puntos y líneas en esa geometría. Con esta interpretación, los 6 ciclos en el gráfico de Heawood corresponden a triángulos en el plano de Fano. Además, el gráfico de Heawood es la construcción de Tits del grupo SL 3 (F 2 ) .
El gráfico de Heawood tiene el número de cruce 3 y es el gráfico cúbico más pequeño con ese número de cruce (secuencia A110507 en la OEIS ). Incluyendo el gráfico de Heawood, hay 8 gráficos distintos de orden 14 con cruce número 3.
El gráfico de Heawood es el gráfico cúbico más pequeño con el gráfico de Colin de Verdière invariante μ = 6. [7]
El gráfico de Heawood es un gráfico de unidad de distancia : se puede incrustar en el plano de modo que los vértices adyacentes estén exactamente a una distancia de uno de ellos, sin dos vértices incrustados en el mismo punto y sin vértices incrustados en un punto dentro de un borde. [8]
Propiedades algebraicas
El grupo de automorfismo del grafo de Heawood es isomorfo al grupo lineal proyectivo PGL 2 (7), un grupo de orden 336. [9] Actúa de forma transitiva sobre los vértices, las aristas y los arcos del grafo. Por lo tanto, el gráfico de Heawood es un gráfico simétrico . Tiene automorfismos que llevan cualquier vértice a cualquier otro vértice y cualquier borde a cualquier otro borde. Más fuertemente, el gráfico de Heawood es transitivo de 4 arcos . [10] Según el censo de Foster , el gráfico de Heawood, al que se hace referencia como F014A, es el único gráfico simétrico cúbico en 14 vértices. [11] [12]
Tiene un grosor de libro 3 y un número de cola 2. [13]
El polinomio característico del gráfico de Heawood es. Es el único gráfico con este polinomio característico, lo que lo convierte en un gráfico determinado por su espectro.
Galería
El poliedro de Szilassi .
El gráfico de Heawood tiene el cruce número 3.
El índice cromático del gráfico de Heawood es 3.
El número cromático del gráfico de Heawood es 2.
Una incrustación del gráfico de Heawood en un toro (mostrado como un cuadrado con condiciones de contorno periódicas ) dividiéndolo en siete regiones mutuamente adyacentes
El gráfico de Heawood y el mapa asociado incrustados en el toro.
- "> Reproducir medios
Video de Heawood Graph en Torus
Referencias
- ^ Weisstein, Eric W. "Gráfico de Heawood" . MathWorld .
- ^ a b Brouwer, Andries E. "Gráfico de Heawood" . Adiciones y correcciones al libro Distancia-Gráficos regulares (Brouwer, Cohen, Neumaier; Springer; 1989)
- ^ Abreu, M .; Aldred, REL; Funk, M .; Jackson, Bill; Labbate, D .; Sheehan, J. (2004), "Gráficos y dígrafos con todos los 2 factores isomórficos", Journal of Combinatorial Theory, Serie B , 92 (2): 395–404, doi : 10.1016 / j.jctb.2004.09.004 , MR 2099150.
- ^ Dejter, Italo J. (2011), "Del gráfico de Coxeter al gráfico de Klein", Journal of Graph Theory , 70 : 1–9, arXiv : 1002.1960 , doi : 10.1002 / jgt.20597 , S2CID 754481.
- ^ Brown, Ezra (2002). "Los muchos nombres de (7,3,1)" (PDF) . Revista de Matemáticas . 75 (2): 83–94. doi : 10.2307 / 3219140 . JSTOR 3219140 . Archivado desde el original (PDF) el 5 de febrero de 2012 . Consultado el 27 de octubre de 2006 .
- ^ Heawood, PJ (1890). "Teoremas de coloración de mapas". Revista Trimestral de Matemáticas . Primera Serie. 24 : 322–339.
- ^ Hein van der Holst (2006). "Gráficos y obstrucciones en cuatro dimensiones" (PDF) . Revista de Teoría Combinatoria, Serie B . 96 (3): 388–404. doi : 10.1016 / j.jctb.2005.09.004 .
- ^ Gerbracht, Eberhard H.-A. (2009). "Once unidades de incrustaciones de distancia del gráfico de Heawood". arXiv : 0912.5395 . Código Bibliográfico : 2009arXiv0912.5395G . Cite journal requiere
|journal=( ayuda ). - ^ Bondy, JA ; Murty, USR (1976). Teoría de grafos con aplicaciones . Nueva York: Holanda Septentrional. pag. 237 . ISBN 0-444-19451-7. Archivado desde el original el 13 de abril de 2010 . Consultado el 18 de diciembre de 2019 .
- ^ Conder, Marston; Morton, Margaret (1995). "Clasificación de gráficos simétricos trivalentes de pequeño orden" (PDF) . Revista Australasia de Combinatoria . 11 : 146.
- ^ Royle, G. "Gráficos simétricos cúbicos (el censo de Foster)". Archivado el 20 de julio de 2008 en la Wayback Machine.
- ^ Conder, M. y Dobcsányi, P. "Gráficos simétricos trivalentes hasta 768 vértices". J. Combin. Matemáticas. Combin. Computación. 40, 41-63, 2002.
- ^ Jessica Wolz, Diseños lineales de ingeniería con SAT . Tesis de maestría, Universidad de Tübingen, 2018