En el campo matemático de la teoría de grafos , el grafo de Möbius-Kantor es un grafo cúbico bipartito simétrico con 16 vértices y 24 aristas que llevan el nombre de August Ferdinand Möbius y Seligmann Kantor . Se puede definir como el grafo de Petersen generalizado G (8,3): es decir, está formado por los vértices de un octágono , conectados a los vértices de una estrella de ocho puntas en la que cada punto de la estrella está conectado a la señala a tres pasos de ella.
Gráfico de Möbius-Kantor | |
---|---|
Lleva el nombre de | August Ferdinand Möbius y S. Kantor |
Vértices | dieciséis |
Bordes | 24 |
Radio | 4 |
Diámetro | 4 |
Circunferencia | 6 |
Automorfismos | 96 |
Número cromático | 2 |
Índice cromático | 3 |
Género | 1 |
Espesor del libro | 3 |
Número de cola | 2 |
Propiedades | Simétrico Hamiltoniano Bipartito Cúbico Unidad de distancia Gráfico de Cayley Perfecto Orientablemente simple |
Tabla de gráficos y parámetros |
Configuración de Möbius-Kantor
Möbius (1828) preguntó si existe un par de polígonos con p lados cada uno, con la propiedad de que los vértices de un polígono se encuentran en las líneas que atraviesan los bordes del otro polígono, y viceversa. Si es así, los vértices y los bordes de estos polígonos formarían una configuración proyectiva . Para p = 4 no hay solución en el plano euclidiano , pero Kantor (1882) encontró pares de polígonos de este tipo, para una generalización del problema en el que los puntos y aristas pertenecen al plano proyectivo complejo . Es decir, en la solución de Kantor, las coordenadas de los vértices del polígono son números complejos . La solución de Kantor para p = 4, un par de cuadriláteros inscritos mutuamente en el plano proyectivo complejo, se llama configuración de Möbius-Kantor . El gráfico de Möbius-Kantor deriva su nombre de ser el gráfico de Levi de la configuración de Möbius-Kantor. Tiene un vértice por punto y un vértice por triple, con una arista que conecta dos vértices si corresponden a un punto y a un triple que contiene ese punto.
La configuración también puede describirse algebraicamente en términos del grupo abeliano con nueve elementos. Este grupo tiene cuatro subgrupos de orden tres (los subconjuntos de elementos del formulario, , , y respectivamente), cada uno de los cuales se puede utilizar para dividir los nueve elementos del grupo en tres clases laterales de tres elementos por clase lateral. Estos nueve elementos y doce cosets forman una configuración, la configuración Hesse . La eliminación del elemento cero y las cuatro clases laterales que contienen cero da lugar a la configuración de Möbius-Kantor.
Como subgrafo
El gráfico de Möbius-Kantor es un subgráfico del gráfico del hipercubo de cuatro dimensiones , formado al eliminar ocho bordes del hipercubo ( Coxeter 1950 ). Dado que el hipercubo es un gráfico de unidad de distancia , el gráfico de Möbius-Kantor también se puede dibujar en el plano con todas las aristas de longitud unitaria, aunque tal dibujo necesariamente tendrá algunos pares de aristas cruzadas.
El gráfico de Möbius-Kantor también ocurre muchas veces como en el subgráfico inducido del gráfico de Hoffman-Singleton . Cada uno de estos casos es de hecho un vector propio del gráfico de Hoffman-Singleton, con el valor propio asociado -3. Cada vértice que no está en el gráfico de Möbius-Kantor inducido es adyacente a exactamente cuatro vértices en el gráfico de Möbius-Kantor, dos de cada uno en la mitad de una bipartición del gráfico de Möbius-Kantor.
Topología
El gráfico de Möbius-Kantor no se puede incrustar sin cruces en el plano; tiene el número de cruce 4 y es el gráfico cúbico más pequeño con ese número de cruce (secuencia A110507 en la OEIS ). Además, proporciona un ejemplo de un gráfico cuyos números de cruce de subgráficos difieren de él en dos o más. [1] Sin embargo, es un gráfico toroidal : tiene una incrustación en el toro en la que todas las caras son hexágonos ( Marušič & Pisanski 2000 ). El gráfico dual de esta incrustación es el gráfico hiperoctaédrico K 2,2,2,2 .
Hay una incrustación aún más simétrica del gráfico de Möbius-Kantor en el doble toro que es un mapa regular , con seis caras octagonales , en el que las 96 simetrías del gráfico se pueden realizar como simetrías de la incrustación; Coxeter (1950) atribuye esta incorporación a Threlfall (1932) . Su grupo de simetría de 96 elementos tiene un gráfico de Cayley que se puede incrustar en el doble toro, y Tucker (1984) demostró que es el grupo único con el género dos. El gráfico de Cayley en 96 vértices es un gráfico de bandera del mapa regular del género 2 que tiene el gráfico de Möbius-Kantor como esqueleto. Esto significa que se puede obtener del mapa regular como un esqueleto del dual de su subdivisión baricéntrica. Una escultura de DeWitt Godfrey y Duane Martinez que muestra la incrustación de doble toro de las simetrías del gráfico de Möbius-Kantor se presentó en el Museo Técnico de Eslovenia como parte de la VI Conferencia Internacional Eslovena sobre Teoría de Gráficos en 2007. En 2013, una versión rotativa de la escultura se dio a conocer en la Universidad de Colgate .
El gráfico de Möbius-Kantor admite una incrustación en un triple toro ( toro de género 3) que es un mapa regular que tiene cuatro caras de 12 gonales, y es el dual de Petrie de la incrustación de doble toro descrito anteriormente; ( Marušič y Pisanski 2000 ).
Lijnen y Ceulemans (2004) , motivados por una investigación de las estructuras químicas potenciales de los compuestos de carbono, estudiaron la familia de todas las incrustaciones del gráfico de Möbius-Kantor en 2 variedades ; demostraron que hay 759 incrustaciones desiguales.
Propiedades algebraicas
El grupo de automorfismo del grafo de Möbius-Kantor es un grupo de orden 96. [2] Actúa de forma transitiva sobre los vértices, las aristas y los arcos del grafo. Por lo tanto, la gráfica de Möbius-Kantor es simétrica . Tiene automorfismos que llevan cualquier vértice a cualquier otro vértice y cualquier borde a cualquier otro borde. Según el censo de Foster , el gráfico de Möbius-Kantor es el gráfico simétrico cúbico único con 16 vértices, y el gráfico simétrico cúbico más pequeño que no es también transitivo a la distancia . [3] El gráfico de Möbius-Kantor también es un gráfico de Cayley .
El gráfico de Petersen generalizado G ( n, k ) es transitivo al vértice si y solo si n = 10 y k = 2 o si k 2 ≡ ± 1 (mod n ) y es transitivo al borde solo en los siete casos siguientes: ( n , k ) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5) o (24,5) ( Frucht, Graver Y Watkins 1971 ). Por tanto, el gráfico de Möbius-Kantor es uno de los siete únicos gráficos de Petersen generalizados simétricos. Su incrustación simétrica de doble toro es, en consecuencia, uno de los siete mapas cúbicos regulares en los que el número total de vértices es el doble del número de vértices por cara ( McMullen 1992 ). Entre los siete gráficos de Petersen generalizados simétricos se encuentran el gráfico cúbico , el gráfico de Petersen , el gráfico dodecaédrico , el gráfico de Desargues y el gráfico de Nauru .
El polinomio característico del gráfico de Möbius-Kantor es igual a
Ver también
- Grupo Pauli
Notas
- ^ McQuillan, Dan; Richter, R. Bruce (1992), "Sobre los números de cruce de ciertos gráficos de Petersen generalizados", Matemáticas discretas , 104 (3): 311–320, doi : 10.1016 / 0012-365X (92) 90453-M , MR 1171327.
- ^ Royle, G. F016A data [ enlace muerto permanente ]
- ^ Conder, M. y Dobcsányi, P. "Gráficos simétricos trivalentes hasta 768 vértices". J. Combin. Matemáticas. Combin. Computación. 40, 41-63, 2002.
Referencias
- Coxeter, HSM (1950), "Configuraciones auto-duales y gráficos regulares", Boletín de la American Mathematical Society , 56 (5): 413–455, doi : 10.1090 / S0002-9904-1950-09407-5.
- Frucht, Robert ; Graver, Jack E .; Watkins, Mark E. (1971), "The groups of the generalized Petersen graphs", Proceedings of the Cambridge Philosophical Society , 70 (02): 211-218, doi : 10.1017 / S0305004100049811 , MR 0289365.
- Kantor, Seligmann (1882), "Über die Configurationen (3, 3) mit den Indices 8, 9 und ihren Zusammenhang mit den Curven dritter Ordnung", Sitzungsberichte der Mathematisch-Naturwissenschaftlichen Classe der Kaiserlichen Akademie der Wissenschaften , 84 (1) Wien : 915–932.
- Lijnen, Erwin; Ceulemans, Arnout (2004), "Incrustaciones orientadas de 2 celdas de un gráfico y su clasificación de simetría: generación de algoritmos y estudio de caso del gráfico de Möbius-Kantor", Journal of Chemical Information and Modeling , 44 (5): 1552-1564, doi : 10.1021 / ci049865c , PMID 15446812.
- Marušič, Dragan ; Pisanski, Tomaž (2000), "The notable generalized Petersen graph G (8,3)" , Mathematica Slovaca , 50 : 117-121.
- McMullen, Peter (1992), "Los poliedros regulares de tipo { p , 3} con 2 p vértices", Geometriae Dedicata , 43 (3): 285–289, doi : 10.1007 / BF00151518.
- Möbius, August Ferdinand (1828), "Kann von zwei dreiseitigen Pyramiden eine jede in Bezug auf die andere um- und eingeschrieben zugleich heissen?" (PDF) , Journal für die reine und angewandte Mathematik , 3 : 273–278. En Gesammelte Werke (1886), vol. 1, págs. 439–446.
- Tucker, Thomas W. (1984), "Sólo hay un grupo del género dos", Journal of Combinatorial Theory, Serie B , 36 (3): 269-275, doi : 10.1016 / 0095-8956 (84) 90032-7.
- Threlfall, William (1932), "Gruppenbilder", Abhandlungen der Mathematisch-Physischen Klasse der Sächsischen Akademie der Wissenschaften , 41 (6): 1-59.
- Jessica Wolz, Diseños lineales de ingeniería con SAT. Tesis de maestría, Universidad de Tübingen, 2018
enlaces externos
- Weisstein, Eric W. "Gráfico de Möbius-Kantor" . MathWorld .
- Revelando la escultura de la Universidad de Colgate