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 se puede incrustar en la superficie orientable del género 3, en el que forman gráficos duales .
El gráfico de Klein cúbico
El gráfico de Klein (cúbico) | |
---|---|
Lleva el nombre de | Felix Klein |
Vértices | 56 |
Bordes | 84 |
Radio | 6 |
Diámetro | 6 |
Circunferencia | 7 |
Automorfismos | 336 |
Número cromático | 3 |
Índice cromático | 3 |
Espesor del libro | 3 |
Número de cola | 2 |
Propiedades | Gráfico de Cayley Hamiltoniano cúbico simétrico |
Tabla de gráficos y parámetros |
Este gráfico es un gráfico 3- regular con 56 vértices y 84 aristas, llamado así por Felix Klein .
Es un gráfico hamiltoniano . Tiene número cromático 3, índice cromático 3, radio 6, diámetro 6 y circunferencia 7. También es un gráfico conectado a 3 vértices y a 3 aristas . Tiene un grosor de libro 3 y un número de cola 2. [1]
Se puede incrustar en la superficie orientable del género -3 (que se puede representar como el cuartico de Klein ), donde forma el "mapa de Klein" con 24 caras heptagonales, símbolo de Schläfli {7,3} 8 .
Según el censo de Foster , el gráfico de Klein, al que se hace referencia como F056B, es el único gráfico simétrico cúbico en 56 vértices que no es bipartito . [2]
Puede derivarse del gráfico de Coxeter de 28 vértices . [3]
Propiedades algebraicas
El grupo de automorfismo del gráfico de Klein es el grupo PGL 2 (7) de orden 336, que tiene PSL 2 (7) como subgrupo normal. Este grupo actúa transitivamente en sus mitades, por lo que el gráfico de Klein es un gráfico simétrico .
El polinomio característico de este gráfico de Klein de 56 vértices es igual a
Galería
Dibujo alternativo del gráfico de Klein cúbico, que muestra que es hamiltoniano, con índice cromático 3.
El gráfico de Klein de 7 valente
El gráfico de Klein (7-valente) | |
---|---|
Lleva el nombre de | Felix Klein |
Vértices | 24 |
Bordes | 84 |
Radio | 3 |
Diámetro | 3 |
Circunferencia | 3 |
Automorfismos | 336 |
Número cromático | 4 |
Índice cromático | 7 |
Propiedades | Hamiltoniano simétrico |
Tabla de gráficos y parámetros |
Esta gráfica es una gráfica 7- regular con 24 vértices y 84 aristas, que lleva el nombre de Felix Klein .
Es un gráfico 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 género-3, donde forma el dual del "mapa de Klein", con 56 caras triangulares, símbolo de Schläfli {3,7} 8 . [4]
Es el gráfico único de distancia regular con matriz de intersección; sin embargo, no es un gráfico transitivo a la distancia . [5]
Propiedades algebraicas
El grupo de automorfismo del gráfico de Klein 7-valente es el mismo grupo de orden 336 que para el mapa de Klein cúbico, actuando también de manera transitiva en sus medios bordes.
El polinomio característico de este gráfico de Klein de 24 vértices es igual a. [6]
Referencias
- ^ Wolz, Jessica; Diseños lineales de ingeniería con SAT. Tesis de maestría, Universidad de Tübingen, 2018
- ^ Conder, M .; Dobcsányi, P. (2002), "Gráficos simétricos trivalentes hasta 768 vértices", J. Combin. Matemáticas. Combin. Computación. , 40 : 41–63.
- ^ Dejter, Italo. "Del gráfico de Coxeter al gráfico de Klein". CiteSeer. CiteSeerX 10.1.1.188.2580 . Cite journal requiere
|journal=
( ayuda ) - ^ Schulte, Egon; Testamentos, JM (1985). "Una realización poliédrica del mapa {3, 7} 8 de Felix Klein en una superficie de Riemann del género 3" . J. London Math. Soc . t2-32 (3): 539-547. doi : 10.1112 / jlms / s2-32.3.539 .
- ^ Brouwer, Andries ; Cohen, Arjeh; Neumaier, Arnold (1989). Gráficos de distancia regular . Springer-Verlag . pag. 386 . ISBN 978-0-387-50619-7.
- ^ van Dam, ER; Haemers, WH; Koolen, JH; Spence, E. (2006). "Caracterización de la regularidad de la distancia de los gráficos por el espectro" . J. Combin. Teoría Ser. Una . 113 (8): 1805–1820. doi : 10.1016 / j.jcta.2006.03.008 .