En el campo matemático de la teoría de grafos , el gráfico de Heawood es un gráfico no dirigido con 14 vértices y 21 aristas, llamado así en honor a Percy John Heawood . [1]
La gráfica es cúbica y todos los ciclos de la gráfica 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 la jaula de 6 , el gráfico cúbico más pequeño de circunferencia 6. Es un gráfico transitivo de distancia (ver el censo de Foster ) y, por lo tanto, de distancia regular . [2]
Hay 24 coincidencias perfectas en el gráfico de Heawood; para cada coincidencia, el conjunto de aristas que no están en la coincidencia 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, colorear sus bordes en 3 colores ) de ocho maneras diferentes. [2] Cada dos coincidencias perfectas y cada dos ciclos hamiltonianos pueden transformarse 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 está separado de exactamente otros tres 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 una arista por cada par disjunto de 6 ciclos es el gráfico de Coxeter . [4]
El gráfico de Heawood es un gráfico toroidal ; es decir, se puede incrustar sin cruces sobre un toroide . El resultado es el mapa regular {6,3} 2,1 , con 7 caras hexagonales . [5] Cada cara del mapa es adyacente a todas las demás caras, por lo que colorear el mapa requiere 7 colores. El mapa y el gráfico fueron descubiertos por Percy John Heawood en 1890, quien demostró que ningún mapa sobre el toroide podía requerir más de siete colores y, por tanto, este mapa es máximo. [6] [7]
El mapa puede representarse fielmente como el poliedro de Szilassi , [8] el único poliedro conocido aparte del tetraedro tal que cada par de caras es adyacente.
La gráfica de Heawood es la gráfica de Levi del plano de Fano , [5] la gráfica que representa las incidencias entre puntos y rectas en esa geometría. Con esta interpretación, los 6 ciclos del gráfico de Heawood corresponden a triángulos en el plano de Fano. Además, el gráfico de Heawood es el edificio de tetas 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 la gráfica de Heawood, hay 8 gráficas distintas de orden 14 con cruce número 3.
El gráfico de Heawood es el gráfico cúbico más pequeño con invariante del gráfico de Colin de Verdière μ = 6 . [9]
El gráfico de Heawood es un gráfico de distancia unitaria : se puede incrustar en el plano de manera que los vértices adyacentes estén exactamente a una distancia uno de otro, sin que haya dos vértices incrustados en el mismo punto y ningún vértice incrustado en un punto dentro de un borde. [10]
El grupo de automorfismo del gráfico de Heawood es isomorfo al grupo lineal proyectivo PGL 2 (7), un grupo de orden 336. [11] Actúa transitivamente sobre los vértices, las aristas y los arcos del gráfico. Por tanto, la gráfica de Heawood es una gráfica simétrica . Tiene automorfismos que llevan cualquier vértice a cualquier otro vértice y cualquier arista a cualquier otra arista. Más claramente, el gráfico de Heawood es transitivo de 4 arcos . [12] 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. [13] [14]
Tiene un grosor de libro 3 y una cola número 2. [15]
El polinomio característico del gráfico de Heawood es . Es el único gráfico con este polinomio característico, por lo que es un gráfico determinado por su espectro.
