Grafo de Möbius-Kantor

Grafo de Möbius-Kantor
Nombre en honor a	August Möbius y Seligmann Kantor
Vértices	16
Aristas	24
Radio	4
Diámetro	4
Cintura	6
Automorfismos	96
Número cromático	2
Índice cromático	3
Propiedades	Simétrico Hamiltoniano Bipartito Cúbico Distancia unitario Grafo de Cayley Perfecto Simple orientable

En el campo matemático de la teoría de grafos, el grafo de Möbius-Kantor es un grafo cúbico bipartito y simétrico que consta de 16 vértices y 24 aristas, que lleva el nombre de August Möbius y de 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, conectado a los vértices de una estrella de ocho puntas en la que cada punta de la estrella está conectada a los puntos situados a tres pasos de él.

Configuración de Möbius-Kantor

La configuración de Möbius-Kantor

Möbius (1828) se preguntó si existe un par de polígonos con p lados cada uno, que tengan la propiedad de que los vértices de un polígono se encuentren en las líneas que pasan por los bordes del otro polígono, y viceversa. Si es así, los vértices y las aristas de estos polígonos formarían una configuración proyectiva. Para p = 4 no hay solución en el espacio bidimensional, pero Kantor (1882) encontró pares de polígonos de este tipo, para una generalización del problema en la 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 mutuamente inscritos en el plano proyectivo complejo, se denomina configuración de Möbius-Kantor. El grafo de Möbius-Kantor deriva su nombre de ser el grafo de Levi de la configuración de Möbius-Kantor. Tiene un vértice por cada punto y un vértice por triplete, con una arista que une dos vértices si corresponden a un punto y a un triplete que contiene ese punto.

La configuración también se puede describir algebraicamente en términos del grupo abeliano $\mathbb {Z} _{3}\times \mathbb {Z} _{3}$ con nueve elementos.

Este grupo tiene cuatro subgrupos de orden tres (los subconjuntos de elementos de la forma $(i,0)$, $(i,i)$, $(i,2i)$ y $(0,i)$ respectivamente), cada uno de los cuales se puede usar para dividir los nueve elementos del grupo en tres clases laterales de tres elementos por clase. Estos nueve elementos y doce clases laterales forman la denominada configuración de 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 un subgrafo

El grafo de Möbius-Kantor es un subgrafo del grafo hipercubo de cuatro dimensiones, formado al eliminar ocho aristas del hipercubo (Coxeter, 1950). Dado que el hipercubo es un grafo de distancia unitaria, el grafo de Möbius-Kantor también se puede dibujar en el plano con todas las aristas de igual longitud, aunque tal dibujo necesariamente tendrá algunos pares de aristas que se cruzan.

También aparece muchas veces como en el subgrafo inducido del grafo de Hoffman-Singleton. Cada uno de estos casos es, de hecho, un vector propio del grafo de Hoffman-Singleton, con un valor propio asociado -3. Cada vértice "no" en el grafo de Möbius-Kantor inducido es adyacente a exactamente cuatro vértices "en" el grafo de Möbius-Kantor, dos en cada mitad de una bipartición del grafo de Möbius-Kantor.

Topología

El gráfico de Möbius-Kantor embebido en un toro. Las aristas que se extienden hacia arriba desde el cuadrado central deben verse como conectadas con la arista correspondiente que se extiende hacia abajo desde el cuadrado, y las aristas que se extienden hacia la izquierda desde el cuadrado deben verse como conectadas con la arista correspondiente que se extiende hacia la derecha

El grafo de Möbius-Kantor no se puede embeber sin cruces en el plano; tiene número de cruce 4, y es el grafo cúbico más pequeño con ese número de cruce (sucesión A110507 en OEIS). Además, proporciona un ejemplo de un grafo cuyos números de cruce de todos los subgrafos difieren de él en dos o más.​

Sin embargo, es un grafo toroidal: tiene una incrustación en el toro en la que todas las caras son hexágonos (Marušič y Pisanski, 2000). El grafo dual de esta incrustación es el grafo hiperoctaédrico K_2,2,2,2.

Hay una incrustación aún más simétrica del grafo de Möbius-Kantor en un toro doble, que es un mapa regular, con seis caras octogonales, en el que las 96 simetrías del grafo se pueden realizar como simetrías de la incrustación;Coxeter (1950) atribuye esta proposición a Threlfall (1932). Su grupo de simetría de 96 elementos tiene un grafo de Cayley que puede incrustarse en el toro doble, y Tucker (1984) demostró que es el grupo único con genus dos. El grafo de Cayley con 96 vértices es un grafo de bandera del mapa regular de género 2 que tiene el grafo 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 el embebido en un toro doble de las simetrías del grafo de Möbius-Kantor se inauguró en el Museo Técnico de Eslovenia como parte de la 6ª Conferencia Internacional de Eslovenia sobre Teoría de Grafos en 2007. En 2013, una versión giratoria de la escultura fue presentada en la Universidad Colgate.

El grafo de Möbius-Kantor admite una incrustación en un toro triple (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 sobre el toro doble descrita anteriormente;(Marušič y Pisanski, 2000).Lijnen y Ceulemans (2004), motivado por una investigación de las posibles estructuras químicas de los compuestos de carbono, estudió la familia de todas las incrustaciones del grafo de Möbius-Kantor en 2-variedades; y demostró que hay 759 incrustaciones no equivalentes.

Propiedades algebraicas

El grupo de automorfismos del grafo de Möbius-Kantor es un grupo de orden 96.​ Actúa transitivamente sobre los vértices, sobre las aristas y sobre los arcos del grafo. Por tanto, el grafo de Möbius-Kantor es un grafo simétrico. Tiene automorfismos que llevan cualquier vértice a cualquier otro vértice y cualquier arista a cualquier otra arista. Según el censo de Foster, el grafo de Möbius-Kantor es el único grafo simétrico cúbico con 16 vértices y el grafo simétrico cúbico más pequeño que no es también distancia-transitivo.​ También es un grafo de Cayley.

El grafo de Petersen generalizado G(n,k) es transitivo de vértices si y solo si n = 10 y k =2 o si k² ≡ ±1 ( mod n) y es transitivo de aristas solo en los siguientes siete casos: (n,k) = (4,1), (5,2), (8,3), (10 ,2), (10,3), (12,5) o (24,5) (Frucht, Graver y Watkins, 1971). Entonces, el grafo de Möbius-Kantor es uno de los siete grafos de Petersen generalizados simétricos. Su embebido sobre un toro doble simétrico es correspondientemente 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 grafos de Petersen generalizados simétricos están el grafo cúbico $G(4,1)$, el grafo de Petersen $G(5,2)$, el grafo dodecaédrico $G(10,2)$, el grafo de Desargues $G(10,3)$ y el grafo de Nauru $G(12,5)$.

El polinomio característico del grafo de Möbius-Kantor es igual a

$(x-3)(x-1)^{3}(x+1)^{3}(x+3)(x^{2}-3)^{4}.\$

Véase también

• Grupo de Pauli

Bibliografía

• Coxeter, H. S. M. (1950), «Self-dual configurations and regular graphs», Bulletin of the 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, MR 0289365, doi:10.1017/S0305004100049811 ..
• 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, Wien 84 (1): 915-932 ..
• Lijnen, Erwin; Ceulemans, Arnout (2004), «Oriented 2-Cell Embeddings of a Graph and Their Symmetry Classification: Generating Algorithms and Case Study of the Möbius-Kantor Graph», Journal of Chemical Information and Modeling 44 (5): 1552-1564, PMID 15446812, doi:10.1021/ci049865c ..
• Marušič, Dragan; Pisanski, Tomaž (2000), «The remarkable generalized Petersen graph G(8,3)», Mathematica Slovaca 50: 117-121 ..
• McMullen, Peter (1992), «The regular polyhedra of type {p, 3} with 2p vertices», 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?», 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), «There is only one group of genus two», Journal of Combinatorial Theory, Series 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. «Möbius-Kantor Graph». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Inauguración de la escultura de la Universidad de Colgate

• Datos: Q3115519