Gráficas de Klein

Superficie del género 3

En el campo matemático de la teoría de grafos , los grafos de Klein son dos grafos regulares diferentes pero relacionados , cada uno con 84 aristas. Cada uno puede ser embebido en la superficie orientable de género 3, en la que forman grafos duales .

El gráfico cúbico de Klein

Se trata de un gráfico cúbico ( 3- regular ) con 56 vértices y 84 aristas, llamado así en honor a Felix Klein .

Es hamiltoniano , tiene número cromático 3, índice cromático 3, radio 6, diámetro 6 y circunferencia 7. También es un grafo conexo por 3 vértices y conexo por 3 aristas . Tiene un grosor de libro de 3 y un número de cola de 2. ^[1]

Se puede incrustar en la superficie orientable del género -3 (que se puede representar como la cuártica de Klein ), donde forma la función de Klein con 24 caras heptagonales, símbolo de Schläfli {7,3} ₈ .

Según el censo de Foster , el gráfico de Klein, referenciado como F056B, es el único gráfico cúbico simétrico en 56 vértices que no es bipartito . ^[2]

Se puede derivar del gráfico de Coxeter de 28 vértices . ^[3]

Propiedades algebraicas

El grupo de automorfismos del grafo de Klein es el grupo PGL ₂ (7) de orden 336, que tiene como subgrupo normal a PSL ₂ (7) . Este grupo actúa transitivamente sobre sus semiaristas, por lo que el grafo de Klein es un grafo simétrico .

El polinomio característico de este gráfico de Klein de 56 vértices es igual a ${\displaystyle x^{7}\,(x-3)\,(x+2)^{6}\left(x^{2}-2\right)^{6}\left(x^{2}+x-4\right)^{7}\left(x^{2}-2x-1\right)^{8}}$

El gráfico de Klein 7-regular

Se trata de un gráfico regular de 7 elementos con 24 vértices y 84 aristas, llamado así en honor a Felix Klein .

Es hamiltoniano , tiene número cromático 4, índice cromático 7, radio 3, diámetro 3 y circunferencia 3.

Se puede incrustar en la superficie orientable de género 3, donde forma el dual de la función Klein, con 56 caras triangulares, símbolo de Schläfli { 3,7} _8. ^[4]

Es el único gráfico regular de distancia con matriz de intersección ; sin embargo, no es un gráfico transitivo de distancia . ^[5] ${\displaystyle \{7,4,1;1,2,7\}}$

Propiedades algebraicas

El grupo de automorfismos del grafo de Klein 7-valente es el mismo grupo de orden 336 que el del mapa cúbico de Klein, actuando igualmente transitivamente sobre sus semiaristas.

El polinomio característico de este gráfico de Klein de 24 vértices es igual a . ^[6] ${\displaystyle (x-7)(x+1)^{7}(x^{2}-7)^{8}}$

Teselación cuártica de Klein con 56 triángulos (dual del mapa de Klein)

Referencias

1. Wolz, Jessica; Diseños lineales de ingeniería con SAT. Tesis de maestría, Universidad de Tübingen, 2018
2. Conder, M. ; Dobcsányi, P. (2002). "Grafos simétricos trivalentes de hasta 768 vértices". J. Combin. Matemáticas. Combin. Comput . 40 : 41–63..
3. Dejter, Italo J. (2012). "Del grafo de Coxeter al grafo de Klein". Revista de teoría de grafos . 70 (1): 1–9. arXiv : 1002.1960 . doi :10.1002/jgt.20597. MR  2916063.
4. Schulte, Egon; Wills, JM (1985). "Una realización poliédrica del mapa {3, 7}8 de Felix Klein en una superficie de Riemann de género 3". J. London Math. Soc . s2-32 (3): 539–547. doi :10.1112/jlms/s2-32.3.539.
5. Brouwer, Andries ; Cohen, Arjeh; Neumaier, Arnold (1989). Gráficos regulares de distancia . Springer-Verlag . pag. 386.ISBN​ 978-0-387-50619-7.
6. van Dam, ER; Haemers, WH; Koolen, JH; Spence, E. (2006). "Caracterización de la regularidad de la distancia de los grafos mediante el espectro". J. Combin. Theory Ser. A . 113 (8): 1805–1820. doi : 10.1016/j.jcta.2006.03.008 .