Grafo 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, nombrado en honor de Percy John Heawood.[1]
| Grafo de Heawood | ||
|---|---|---|
| Nombre en honor a | Percy John Heawood | |
| Vértices | 14 | |
| Aristas | 21 | |
| Radio | 3 | |
| Diámetro | 3 | |
| Cintura | 6 | |
| Automorfismos | 336 (PGL2(7)) | |
| Número cromático | 2 | |
| Índice cromático | 3 | |
| Propiedades | Bipartito Cúbico Jaula Distancia-transitivo Distancia-regular Toroidal Hamiltoniano Simétrico | |
Propiedades combinatorias
Este grafo es cúbico, todos los ciclos en el grafo tienen seis o más aristas. Todos los grafos cúbicos más pequeños tienen ciclos más cortos, por lo que este grafo es el 6-jaula, el menor grafo cúbico de cintura 6. Es un grafo distancia-transitivo (ver el censo Foster) y por lo tanto distancia-regular.[2]
Hay 24 apareamientos perfectos en el grafo de Heawood; por cada apareamiento, el conjunto de aristas que no están en el apareamiento forman un ciclo hamiltoniano. Por ejemplo, el diagrama muestra los vértices del grafo colocados en un ciclo, con las diagonales internas del ciclo formando un apareamiento. Subdividiendo las aristas del ciclo en dos apareamientos, podemos particionar el grafo de Heawood en tres apareamientos perfectos (esto es, 3-colorear sus aristas) en ocho formas distintas.[2] Dos apareamientos perfectos cualesquiera, y dos ciclos hamiltonianos cualesquiera, pueden transformarse en el otro por una simetría del grafo.[3]
Hay 28 ciclos de seis vértices en el grafo de Heawood. Cada 6-ciclo es disjunto de exactamente otros tres 6-ciclos; entre esos tres 6-ciclos, cada uno es la diferencia simétrica de los otros dos. El grafo con un nodo por cada 6-ciclo, y una arista por cada par disjunto de 6-ciclos, es el grafo de Coxeter.[4]
Propiedades geométricas y topológicas
El grafo de Heawood es un grafo toroidal; o sea, puede ser encastrado sin cruces sobre un toro. Un encastramiento de este tipo coloca los vèrtices y aristas en el espacio euclídeo tri-dimensional, como el conjunto de vértices y aristas de un poliedro no-convexo con la topología de un toro, el poliedro de Szilassi.
El grafo es nombrado en honor de Percy John Heawood, quien en 1890 probó que en cada subdivisión del toro en polígonos, las regiones poligonales pueden ser coloreadas por, a lo sumo, siete colores.[5][6] El grafo de Heawood forma una subdivisión del toro con siete regiones mutuamente adyacentes, mostrando que esta unión es estrecha.
El grafo de Heawood es también el grafo de Levi del plano de Fano, el grafo que representa la incidencia entre puntos y líneas en esa geometría. En esta interpretación, los 6-ciclos en el grafo de Heawood corresponden a los triángulos en el plano de Fano.
El grafo de Heawood tiene número de cruce 3, y es el menor grafo cúbico con ese número de cruce (sucesión A110507 en OEIS). Incluyendo el grafo de Heawood, hay 8 grafos distintos de orden 14 con número de cruce 3.
El grafo de Heawood es un grafo de distancia unitaria: puede ser encastrado en el plano de tal manera que los vértices adyacentes están exactamente separados por una distancia uno, sin pares de vértices en el mismo punto ni vértices en un punto perteneciente a una arista. Sin embargo, los encastres conocidos de este tipo no poseen ninguna de las simetrías que son inherentes al grafo.[7]
Propiedades algebraicas
El grupo de automorfismos del grafo de Heawood es isomórfico con el grupo lineal proyectivo PGL2(7), un grupo de orden 336.[8] 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 mapean cada vértice a cualquier otro vértice y cada arista a cualquier otra arista. De acuerdo al censo Foster, el grafo de Heawood, referenciado como F014A, es el único grafo simétrico cúbico de 14 vértices.[9][10]
El polinomio característico del grafo de Heawood es . Es el único grafo con este polinomio característico, por lo que es un grafo determinado por su espectro.
Galería
El grafo de Heawood tiene número de cruce 3.
El índice cromático del grafo de Heawood es 3.
El número cromático del grafo de Heawood is 2.
Un encastramiento del grafo de Heawood en un toro (mostrado como un cuadrado con condiciones de borde periódicas) particionándolo en siete regiones adyacentes entre sí.
Referencias
- Weisstein, Eric W. «Heawood Graph». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
- ↑ Brouwer, Andries E.. «Heawood graph». Additions and Corrections to the book Distance-Regular Graphs (Brouwer, Cohen, Neumaier; Springer; 1989).
- Abreu, M.; Aldred, R. E. L.; Funk, M.; Jackson, Bill; Labbate, D.; Sheehan, J. (2004), «Graphs and digraphs with all 2-factors isomorphic», Journal of Combinatorial Theory, Series B 92 (2): 395-404, MR 2099150, doi:10.1016/j.jctb.2004.09.004..
- Dejter, Italo J. (2011), «From the Coxeter graph to the Klein graph», Journal of Graph Theory, arXiv:1002.1960, doi:10.1002/jgt.20597..
- Brown, Ezra (2002). . Mathematics Magazine 75 (2): 83-94. JSTOR 3219140. doi:10.2307/3219140. Archivado desde el original el 5 de febrero de 2012. Consultado el 17 de agosto de 2014.
- Heawood, P. J. (1890). «Map colouring theorems». Quarterly J. Math. Oxford Ser. 24: 322-339.
- Gerbracht, Eberhard H.-A. (2009). Eleven unit distance embeddings of the Heawood graph. arXiv:0912.5395..
- Bondy, J. A.; Murty, U. S. R. (1976). . New York: North Holland. p. 237. ISBN 0-444-19451-7. Archivado desde el original el 13 de abril de 2010. Consultado el 17 de agosto de 2014.
- Royle, G.
- Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.