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, llamado así en honor a Percy John Heawood . [1]
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 6- jaula , el gráfico cúbico más pequeño con una circunferencia de 6. Es un gráfico transitivo en la distancia (véase el censo de Foster ) y, por lo tanto, regular en la distancia . [2]
Hay 24 emparejamientos perfectos en el grafo 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 grafo colocados en un ciclo, con las diagonales internas del ciclo formando un emparejamiento. Al subdividir los bordes del ciclo en dos emparejamientos, podemos dividir el grafo de Heawood en tres emparejamientos perfectos (es decir, 3 colores de sus aristas ) de ocho formas diferentes. [2] Cada dos emparejamientos perfectos, y cada dos ciclos hamiltonianos, se pueden transformar entre sí mediante una simetría del grafo. [3]
Hay 28 ciclos de seis vértices en el grafo de Heawood. Cada ciclo de seis vértices es disjunto de exactamente otros tres ciclos de seis vértices; entre estos tres ciclos de seis vértices, cada uno es la diferencia simétrica de los otros dos. El grafo con un nodo por ciclo de seis vértices y una arista por cada par disjunto de ciclos de seis vértices es el grafo de Coxeter . [4]
El grafo de Heawood es un grafo toroidal , es decir, puede ser incrustado sin cruces en un toro . El resultado es la función regular {6,3} 2,1 , con 7 caras hexagonales . [5] Cada cara de la función es adyacente a todas las demás caras, por lo que para colorear la función se necesitan 7 colores. La función y el grafo fueron descubiertos por Percy John Heawood en 1890, quien demostró que ninguna función en el toro podía requerir más de siete colores y, por lo tanto, esta función es máxima. [6] [7]
El mapa se puede representar fielmente como el poliedro de Szilassi , [8] el único poliedro conocido aparte del tetraedro tal que cada par de caras es adyacente.
El grafo de Heawood es el grafo de Levi del plano de Fano , [5] el grafo que representa las incidencias entre puntos y líneas en esa geometría. Con esta interpretación, los 6-ciclos en el grafo de Heawood corresponden a triángulos en el plano de Fano. Además, el grafo de Heawood es el edificio 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 ). Incluido el gráfico de Heawood, hay 8 gráficos distintos de orden 14 con número de cruce 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. [ 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 de uno, sin dos vértices incrustados en el mismo punto y sin ningún vértice incrustado en un punto dentro de un borde. [10]
El grupo de automorfismos del grafo de Heawood es isomorfo al grupo lineal proyectivo PGL 2 (7), un grupo de orden 336. [11] Actúa transitivamente sobre los vértices, sobre las aristas y sobre los arcos del grafo. Por lo tanto, el grafo de Heawood es un grafo simétrico . Tiene automorfismos que llevan cualquier vértice a cualquier otro vértice y cualquier arista a cualquier otra arista. Más fuertemente, el grafo de Heawood es 4-arco-transitivo . [12] Según el censo de Foster , el grafo de Heawood, referenciado como F014A, es el único grafo cúbico simétrico sobre 14 vértices. [13] [14]
Tiene un grosor de libro de 3 y un número de cola de 2. [15]
El polinomio característico del grafo de Heawood es . Es el único grafo con este polinomio característico, lo que lo convierte en un grafo determinado por su espectro.
