stringtranslate.com

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, llamado así en honor a Percy John Heawood . [1]

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 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]

Propiedades geométricas y topológicas

Mapa de Heawood. Los bordes opuestos del hexágono grande están conectados para formar un toro.

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.

Plano de Fano y dos representaciones de su gráfico de Levi (abajo como gráfico 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 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]

Propiedades algebraicas

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.

Galería

Referencias

  1. ^ Weisstein, Eric W. "Gráfico de Heawood". MathWorld .
  2. ^ por Brouwer, Andries E. "Gráfico de Heawood".Adiciones y correcciones al libro Distance-Regular Graphs (Brouwer, Cohen, Neumaier; Springer; 1989)
  3. ^ Abreu, M.; Aldred, REL; Funk, M.; Jackson, Bill; Labbate, D.; Sheehan, J. (2004), "Gráficos y dígrafos con todos los 2 factores isomorfos", Journal of Combinatorial Theory, Serie B , 92 (2): 395–404, doi : 10.1016/j.jctb.2004.09.004 , MR  2099150.
  4. ^ 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.
  5. ^ ab Coxeter (1950), "Configuraciones autoduales y grafos regulares" (PDF) , Boletín de la Sociedad Matemática Americana , 56 , doi :10.1090/S0002-9904-1950-09407-5
  6. ^ 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 2012-02-05 . Consultado el 2006-10-27 .
  7. ^ Heawood, PJ (1890). "Teorema del mapa-color". Quarterly Journal of Mathematics . Primera serie. 24 : 322–339.
  8. ^ Szilassi, Lajos (1986), "Toroides regulares" (PDF) , Topología estructural , 13 : 69–80
  9. ^ Hein van der Holst (2006). "Gráficos y obstrucciones en cuatro dimensiones" (PDF) . Journal of Combinatorial Theory, Serie B . 96 (3): 388–404. doi : 10.1016/j.jctb.2005.09.004 .
  10. ^ Gerbracht, Eberhard H.-A. (2009), Once incrustaciones de distancia unitaria del gráfico de Heawood , arXiv : 0912.5395 , Bibcode :2009arXiv0912.5395G.
  11. ^ Bondy, JA ; Murty, USR (1976). Teoría de grafos con aplicaciones. Nueva York: North Holland. p. 237. ISBN 0-444-19451-7Archivado desde el original el 13 de abril de 2010. Consultado el 18 de diciembre de 2019 .
  12. ^ Conder, Marston; Morton, Margaret (1995). "Clasificación de grafos simétricos trivalentes de orden pequeño" (PDF) . Australasian Journal of Combinatorics . 11 : 146.
  13. ^ Royle, G. "Gráficos cúbicos simétricos (El censo de Foster)". Archivado el 20 de julio de 2008 en Wayback Machine.
  14. ^ Conder, M. y Dobcsányi, P. "Gráficos simétricos trivalentes de hasta 768 vértices". J. Combin. Math. Combin. Comput. 40, 41-63, 2002.
  15. ^ Jessica Wolz, Diseños lineales de ingeniería con SAT . Tesis de maestría, Universidad de Tübingen, 2018