Conde de Heawood

El gráfico de Heawood  es un gráfico no dirigido con 14 vértices y 21 aristas, llamado así por Percy John Heawood [1] .

Propiedades combinatorias

El gráfico es cúbico y todos los ciclos del gráfico contienen seis o más aristas. Cualquier gráfico cúbico más pequeño contiene ciclos más pequeños, por lo que este gráfico es una celda (3,6) , el gráfico cúbico más pequeño con una circunferencia de 6. También es transitivo en distancia (consulte la lista de Foster ) y, por lo tanto , es regular en distancia [2] . Hay 24 emparejamientos en el gráfico de Heawood , y en todos los emparejamientos, los bordes que no están incluidos en el emparejamiento forman un ciclo hamiltoniano . Por ejemplo, la figura muestra los vértices de un gráfico colocados en un círculo y formando un ciclo, y las diagonales dentro del círculo forman una coincidencia. Si dividimos los bordes del ciclo en dos coincidencias, obtenemos tres coincidencias perfectas (es decir, una coloración de los bordes de 3 colores ) de ocho maneras diferentes [2] . Debido a la simetría del gráfico, dos emparejamientos perfectos cualesquiera y dos ciclos hamiltonianos cualesquiera pueden transformarse de uno a otro [3] .

El gráfico de Heawood tiene 28 ciclos que contienen seis vértices cada uno. Cada uno de estos ciclos no está exactamente relacionado con los otros tres ciclos de 6 vértices. Entre estos tres ciclos, cada uno es la diferencia simétrica de los otros dos. Un grafo en el que cada vértice corresponde a un ciclo de 6 vértices en el grafo de Heawood, y los arcos corresponden a pares desconectados es el grafo de Coxeter [4] .

Propiedades geométricas y topológicas

El gráfico de Heawood es un gráfico toroidal , lo que significa que se puede incrustar sin intersecciones en un toroide . Uno de estos tipos de incrustaciones coloca los vértices y las aristas de un gráfico en un espacio euclidiano tridimensional como un conjunto de vértices y aristas de un politopo no convexo con topología de toro, el politopo de Silashi . El gráfico lleva el nombre de Percy John Heawood , quien demostró en 1890 que siete colores son suficientes para colorear cualquier mosaico de polígono toroide [5] [6] . El gráfico de Heawood forma una partición del toro en siete regiones mutuamente adyacentes, lo que muestra que el límite es exacto. El gráfico de Heawood es también el gráfico de Levi del plano de Fano , es decir, el gráfico que representa la incidencia de puntos y líneas en esta geometría. En esta interpretación, los ciclos de longitud 6 en el gráfico de Heawood corresponden a los triángulos de la superficie de Fano. El gráfico de Heawood tiene un número de cruces de 3 y es el gráfico cúbico más pequeño con este número de cruces [7] . Junto con el gráfico de Heawood, hay 8 gráficos diferentes de orden 14 con un número de cruces de 3. El gráfico de Heawood es un gráfico de distancia unitaria  : se puede incrustar en un plano para que los vértices adyacentes estén exactamente a una distancia de uno, mientras que no caerán dos vértices en el mismo lugar del plano y ningún punto estará dentro de la arista. Sin embargo, las incrustaciones conocidas de este tipo carecen de la simetría inherente a un gráfico [8] .

Propiedades algebraicas

El grupo de automorfismos del grafo de Heawood es isomorfo al grupo lineal proyectivo PGL 2 (7), un grupo de orden 336 [9] . Actúa transitivamente sobre los vértices, aristas y arcos del gráfico, por lo que el gráfico de Heawood es simétrico . Hay automorfismos que llevan cualquier vértice a cualquier otro vértice y cualquier arista a cualquier otra arista. Según la lista de Foster , el gráfico de Heawood, denominado F014A, es el único gráfico cúbico con 14 vértices [10] [11] . El polinomio característico de la matriz gráfica de Heawood es . El espectro del gráfico es Este es el único gráfico con tal polinomio que está determinado por el espectro.

El polinomio cromático del gráfico es:

Galería

• El poliedro de Silashi .

• El gráfico de Heawood tiene 3 cruces .

• 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 (que se muestra como un cuadrado con condiciones de contorno periódicas ), que lo divide en siete regiones mutuamente adyacentes

Notas

1. ↑ Weisstein, Eric W. Heawood Gráfico  en el sitio web Wolfram MathWorld .
2. ↑ 1 2 Brouwer, Andries E. Gráfico de Heawood . Adiciones y correcciones al libro "Distance-Regular Graphs" (Brouwer, Cohen, Neumaier; Springer; 1989) . Consultado el 2 de enero de 2014. Archivado desde el original el 1 de agosto de 2012. (indefinido)
3. ↑ M. Abreu, REL Aldred, M. Funk, Bill Jackson, D. Labbate, J. Sheehan. Gráficos y dígrafos con todos los 2 factores isomorfos // Journal of Combinatorial Theory. - 2004. - T. 92 , núm. 2 . - S. 395-404 . -doi : 10.1016/ j.jctb.2004.09.004 . .
4. ↑ Italo J. Dejter. Del gráfico de Coxeter al gráfico de Klein // Journal of Graph Theory. - 2011. - doi : 10.1002/jgt.20597 . - arXiv : 1002.1960 . .
5. ↑ Ezra Brown. Los muchos nombres de (7,3,1) // Revista de Matemáticas . - 2002. - T. 75 , núm. 2 . - S. 83-94 . -doi : 10.2307/ 3219140 . — .
6. ↑ PJ Heawood. Teoremas para colorear mapas // Quarterly J. Math. Serie Oxford. - 1890. - T. 24 . - S. 322-339 .
7. ↑ Secuencia OEIS A110507 _
8. ↑ Eberhard H., A. Gerbracht. Once incrustaciones de distancia unitaria del gráfico de Heawood. - 2009. - arXiv : 0912.5395 . .
9. ↑ JA Bondy, USR Murty. Teoría de Grafos con Aplicaciones . - Nueva York: Holanda Septentrional, 1976. - Pág. 237. - ISBN 0-444-19451-7 .
10. ↑ Royle, G. "Gráficos simétricos cúbicos (lista de Foster)". Archivado desde el original el 20 de julio de 2008.
11. ↑ Marston Conder y Dobcsányi, P. "Gráficos simétricos trivalentes hasta 768 vértices". J. Combina. Matemáticas. Combinar. computar 40, 41-63, 2002.