Gráfico de Heawood

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 recibe su nombre de Percy John Heawood . ^{[ 1 ]}

El grafo es cúbico y todos los ciclos del grafo tienen seis o más aristas. Cada grafo cúbico más pequeño tiene ciclos más cortos, por lo que este grafo es la jaula de 6 , el grafo cúbico más pequeño de circunferencia 6. Es un grafo transitivo en distancia (véase el censo de Foster ) y, por lo tanto, regular en distancia . ^{[ 2 ]}

En el grafo de Heawood existen 24 emparejamientos perfectos ; para cada emparejamiento, el conjunto de aristas que no pertenecen a él forma un ciclo hamiltoniano . Por ejemplo, la figura muestra los vértices del grafo colocados en un ciclo, cuyas diagonales internas forman un emparejamiento. Al subdividir las aristas del ciclo en dos emparejamientos, podemos particionar el grafo de Heawood en tres emparejamientos perfectos (es decir, colorear sus aristas con 3 colores ) de ocho maneras diferentes. ^{[ 2 ]} Cada par de emparejamientos perfectos, y cada par de ciclos hamiltonianos, pueden transformarse entre sí mediante una simetría del grafo. ^{[ 3 ]}

En el grafo de Heawood hay 28 ciclos de seis vértices. Cada ciclo de 6 vértices es disjunto de exactamente otros tres ciclos de 6 vértices; entre estos tres ciclos de 6 vértices, cada uno es la diferencia simétrica de los otros dos. El grafo con un nodo por ciclo de 6 vértices y una arista por cada par disjunto de ciclos de 6 vértices es el grafo de Coxeter . ^{[ 4 ]}

El grafo de Heawood es un grafo toroidal ; es decir, puede incrustarse sin cruces en un toro . 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, por lo que colorear el mapa requiere 7 colores. El mapa y el grafo fueron descubiertos por Percy John Heawood en 1890, quien demostró que ningún mapa en el toro podría requerir más de siete colores y, por lo tanto, este mapa es maximal. ^{[ 6 ] [ 7 ]}

El mapa se puede realizar fielmente como el poliedro de Szilassi , ^{[ 8 ]} el único poliedro conocido aparte del tetraedro tal que cada par de caras es adyacente.

Plano de Fano y dos representaciones de su grafo de Levi (abajo como un grafo bipartito ).

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 la construcción de Tits _del grupo SL3 ( _F2 ) .

El grafo de Heawood tiene un cruce número 3, y es el grafo cúbico más pequeño con ese número de cruce (secuencia A110507 en la OEIS ) . Incluyendo el grafo de Heawood, hay 8 grafos distintos de orden 14 con un cruce número 3.

El grafo de Heawood es el grafo cúbico más pequeño con invariante de grafo de Colin de Verdière μ = 6. ^{[ 9 ]}

El grafo de Heawood es un grafo de distancia unitaria : puede incrustarse en el plano de tal manera que los vértices adyacentes estén exactamente a una distancia de uno, sin que dos vértices estén incrustados en el mismo punto y sin que ningún vértice esté incrustado en un punto dentro de una arista. ^{[ 10 ]}

El grupo de automorfismos del grafo de Heawood es isomorfo al grupo lineal proyectivo PGL ₂ (7), un grupo de orden 336. ^{[ 11 ]} Actúa transitivamente sobre los vértices, las aristas y los arcos del grafo. Por lo tanto, el grafo de Heawood es un grafo simétrico . Tiene automorfismos que transforman cualquier vértice en cualquier otro vértice y cualquier arista en 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 de 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 gráfico de Heawood es${\displaystyle (x-3)(x+3)(x^{2}-2)^{6}}$Es la única gráfica con este polinomio característico, lo que la convierte en una gráfica determinada por su espectro.

• 
  cruce número 3 y 1-planar
• 
  índice cromático 3
• 
  número cromático 2
• 
  incrustado en un toroide ( mostrado como un cuadrado )
• 
  incrustado en un toroide (comparar con el vídeo )
• 
  poliedro de Szilassi