El gráfico de Nauru requiere al menos ocho cruces en cualquier dibujo del mismo en el plano. Es uno de los tres gráficos no isomórficos empatados por ser el gráfico cúbico más pequeño que requiere ocho cruces. Otra de estas tres gráficas es la gráfica de McGee , también conocida como jaula (3-7) . [4] [5]
Construcción
El gráfico de Nauru es hamiltoniano y puede describirse mediante la notación LCF : [5, −9, 7, −7, 9, −5] 4 . [1]
El gráfico de Nauru también se puede construir como el gráfico de Petersen generalizado G (12, 5) que está formado por los vértices de un dodecágono conectados a los vértices de una estrella de doce puntas en la que cada punta de la estrella está conectada a los puntos cinco. pasos lejos de ello.
También existe una construcción combinatoria del gráfico de Nauru. Tome tres objetos distinguibles y colóquelos en cuatro cajas distinguibles, no más de un objeto por caja. Hay 24 formas de distribuir así los objetos, correspondientes a los 24 vértices del gráfico. Si es posible pasar de un estado a otro moviendo exactamente un objeto desde su ubicación actual a un cuadro vacío, entonces los vértices correspondientes a los dos estados están unidos por una arista. El gráfico de transición de estado resultante es el gráfico de Nauru.
Propiedades algebraicas
El grupo de automorfismo del gráfico de Nauru es un grupo de orden 144. [6] Es isomorfo al producto directo de los grupos simétricos S 4 y S 3 y actúa transitivamente sobre los vértices, las aristas y los arcos del gráfico. . Por lo tanto, el gráfico de Nauru es un gráfico simétrico (aunque no transitivo de distancia ). 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 gráfico de Nauru es el único gráfico simétrico cúbico sobre 24 vértices. [2]
El gráfico de Petersen generalizado G ( n,k ) es transitivo de vértice si y solo si n = 10 y k =2 o si k 2 ≡ ±1 (mod n ) y es transitivo de borde solo en los siguientes siete casos: ( n ,k ) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5), (24,5). [7] Entonces, el gráfico de Nauru es uno de los siete gráficos simétricos de Petersen generalizados. Entre estos siete gráficos se encuentran el gráfico cúbico , el gráfico de Petersen , el gráfico de Möbius-Kantor , el gráfico dodecaédrico y el gráfico de Desargues .
El gráfico de Nauru es un gráfico de Cayley de S 4 , el grupo simétrico de permutaciones de cuatro elementos, generado por tres formas diferentes de intercambiar el primer elemento con uno de los otros tres: (1 2), (1 3) y (1 4).
24 configuraciones de un cubo de Rubik de 2×2×2 accesibles mediante medias vueltas de 180°
Propiedades topológicas
Una incrustación simétrica del gráfico de Nauru en una superficie de género 4, con seis caras dodecagonales.
El grafo de Nauru tiene dos incrustaciones diferentes como un poliedro regular generalizado : una superficie topológica dividida en aristas, vértices y caras de tal manera que hay una simetría que toma cualquier bandera (un triple incidente de un vértice, una arista y una cara) en cualquier otra bandera. [8]
Una de estas dos incrustaciones forma un toroide , por lo que el gráfico de Nauru es un gráfico toroidal : consta de 12 caras hexagonales junto con los 24 vértices y 36 aristas del gráfico de Nauru. El gráfico dual de esta incrustación es un gráfico simétrico de 6 regulares con 12 vértices y 36 aristas.
La otra incrustación simétrica del gráfico de Nauru tiene seis caras dodecagonales , y forma una superficie de género 4. Su dual no es un gráfico simple , ya que cada cara comparte tres aristas con otras cuatro caras, sino un multigrafo . Este dual se puede formar a partir de la gráfica de un octaedro regular reemplazando cada arista con un conjunto de tres aristas paralelas.
El conjunto de caras de cualquiera de estas dos incrustaciones es el conjunto de polígonos de Petrie de la otra incrustación.
Propiedades geométricas
El gráfico de Nauru como gráfico de distancia unitaria, de Žitnik, Horvat y Pisanski (2010).
Como ocurre con todos los gráficos de Petersen generalizados, el gráfico de Nauru se puede representar mediante puntos en el plano de tal manera que los vértices adyacentes estén separados por una unidad de distancia; es decir, es una gráfica de distancia unitaria . [9] Este y los prismas son los únicos gráficos de Petersen generalizados G ( n , p ) que no pueden representarse de tal manera que las simetrías del dibujo formen un grupo cíclico de orden n . En cambio, su representación gráfica de distancia unitaria tiene el grupo diédrico Dih 6 como grupo de simetría.
Historia
La primera persona que escribió sobre la gráfica de Nauru fue RM Foster , en un esfuerzo por recopilar todas las gráficas simétricas cúbicas. [10] La lista completa de gráficos simétricos cúbicos ahora lleva su nombre Foster Census y dentro de esta lista el gráfico de Nauru está numerado como gráfico F24A, pero no tiene un nombre específico. [11] En 1950, HSM Coxeter citó el gráfico por segunda vez, dando la representación hamiltoniana utilizada para ilustrar este artículo y describiéndolo como el gráfico de Levi de una configuración proyectiva descubierta por Zacharias. [12] [13]
En 2003, Ed Pegg escribió en su columna en línea MAA que F24A merece un nombre pero no propuso uno. [14] Finalmente, en 2007, David Eppstein utilizó el nombre gráfico de Nauru porque la bandera de la República de Nauru tiene una estrella de 12 puntas similar a la que aparece en la construcción del gráfico como un gráfico de Petersen generalizado. [1]
Referencias
^ abc Eppstein, D. , Las muchas caras del gráfico de Nauru, 2007.
^ ab Conder, M. y Dobcsányi, P. "Gráficos simétricos trivalentes de hasta 768 vértices". J. Combinar. Matemáticas. Combinar. Computadora. 40, 41-63, 2002.
^ Wolz, Jessica; Ingeniería de Trazados Lineales con SAT. Tesis de maestría, Universidad de Tübingen, 2018
^ Pegg, et al ; Exoo, G. (2009), "Crossing number Graphs", Mathematica Journal , 11 (2), doi : 10.3888/tmj.11.2-2 , archivado desde el original el 6 de marzo de 2019 , consultado el 2 de enero de 2010..
^ Royle, G. Datos F024A Archivado el 6 de marzo de 2011 en Wayback Machine.
^ Frucht, R .; Graver, JE; Watkins, ME (1971), "Los grupos de los gráficos generalizados de Petersen", Actas de la Sociedad Filosófica de Cambridge , 70 (2): 211–218, Bibcode :1971PCPS...70..211F, doi :10.1017/S0305004100049811, S2CID 122686848.
^ 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, S2CID 119591683.
^ Žitnik, Arjana; Horvat, Boris; Pisanski, Tomaž (2010), Todos los gráficos de Petersen generalizados son gráficos de unidades de distancia (PDF) , preimpresiones de IMFM, vol. 1109.
Incrustación simétrica sobre un toro formado pegando los bordes opuestos de un hexágono regular
.svg/1280px-Symmetric_group_4;_Cayley_graph_1,5,21_(Nauru_torus).svg.png)
.svg/1280px-Symmetric_group_4;_Cayley_graph_1,5,21_(Nauru_Petersen).svg.png)
.svg/1280px-Symmetric_group_4;_Cayley_graph_1,5,21_(adjacency_matrix).svg.png)
