En el campo matemático de la teoría de grafos , el grafo de Nauru es un grafo cúbico bipartito simétrico con 24 vértices y 36 aristas. Fue nombrado por David Eppstein después de la estrella de doce puntas en la bandera de Nauru . [1]
Gráfico de Nauru | |
---|---|
Vértices | 24 |
Bordes | 36 |
Radio | 4 |
Diámetro | 4 |
Circunferencia | 6 |
Automorfismos | 144 (S 4 × S 3 ) |
Número cromático | 2 |
Índice cromático | 3 |
Espesor del libro | 3 |
Número de cola | 2 |
Propiedades | Gráfico de Cayley integral hamiltoniano cúbico simétrico Bipartito |
Tabla de gráficos y parámetros |
Tiene número cromático 2, índice cromático 3, diámetro 4, radio 4 y circunferencia 6. [2] También es un gráfico de 3 vértices conectados y 3 bordes conectados . Tiene un grosor de libro 3 y un número de cola 2. [3]
El gráfico de Nauru requiere al menos ocho cruces en cualquier dibujo del mismo en el avión. Es uno de los cinco gráficos no isomórficos empatados por ser el gráfico cúbico más pequeño que requiere ocho cruces. Otro de estos cinco gráficos es el gráfico de McGee , también conocido como la jaula (3-7) . [4] [5]
Construcción
El gráfico de Nauru es hamiltoniano y se puede describir 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 conectado a los vértices de una estrella de doce puntos en el que cada punto de la estrella está conectado a los puntos cinco. pasos lejos de ella.
También hay 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 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 una caja vacía, 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 grafo 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 grafo. . Por lo tanto, el gráfico de Nauru es simétrico (aunque no transitivo a la distancia ). 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 Nauru es el único gráfico simétrico cúbico en 24 vértices. [2]
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), (24,5). [7] Por lo tanto, el gráfico de Nauru es uno de los siete gráficos de Petersen generalizados simétricos. 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 en cuatro elementos, generado por las tres formas diferentes de intercambiar el primer elemento con uno de los otros tres: (1 2), (1 3) y (1 4).
El polinomio característico del gráfico de Nauru es igual a
lo que lo convierte en un gráfico integral, un gráfico cuyo espectro consiste enteramente en números enteros.
Incrustación simétrica en un toro formado al pegar los bordes opuestos de un hexágono regular
Gráfico de Petersen generalizado , coloreado y etiquetado como un gráfico de Cayley de S 4
Matriz de adyacencia . Cada borde está representado por dos entradas colocadas simétricamente en el mismo color
Dibujo en 1 plano con 8 cruces
24 orientaciones de un octaedro rodante en una cuadrícula triangular , dibujada en un toro hexagonal
Propiedades topologicas
El gráfico de Nauru tiene dos incrustaciones diferentes como un poliedro regular generalizado : una superficie topológica dividida en bordes, vértices y caras de tal manera que hay una simetría que toma cualquier bandera (un triple incidente de un vértice, borde y cara) en cualquier otra bandera. [8]
Una de estas dos incrustaciones forma un toro , 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 del género 4. Su dual no es un gráfico simple , ya que cada cara comparte tres aristas con otras cuatro caras, sino un multigraph . Este dual se puede formar a partir del gráfico de un octaedro regular reemplazando cada borde con un conjunto de tres bordes paralelos.
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
Al igual que 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 unidades de distancia; es decir, es un gráfico de unidad de distancia . [9] Este y los prismas son los únicos gráficos de Petersen generalizados G ( n , p ) que no pueden ser representados 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 diedro Dih 6 como su grupo de simetría.
Historia
La primera persona en escribir sobre el gráfico de Nauru fue RM Foster , en un esfuerzo por recopilar todos los gráficos simétricos cúbicos. [10] La lista completa de gráficos simétricos cúbicos ahora lleva su nombre, el Censo Foster 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 MAA en línea que F24A merece un nombre pero no lo propuso. [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
- ^ a b c Eppstein, D. , Las muchas caras del gráfico de Nauru , 2007.
- ^ a b 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.
- ^ Wolz, Jessica; Diseños lineales de ingeniería con SAT. Tesis de maestría, Universidad de Tübingen, 2018
- ^ Sloane, N. J. A. (ed.). "Secuencia A110507 (Número de nodos en el gráfico cúbico más pequeño con el número de cruce n)" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS..
- ^ Pegg, ET ; Exoo, G. (2009), "Crossing gráficos de números" , Mathematica Journal , 11 , Archivado desde el original en 03/06/2019 , recuperada 2010-01-02 CS1 maint: parámetro desalentado ( enlace ).
- ↑ Royle, G. F024A data Archived 2011-03-06 en Wayback Machine.
- ^ Frucht, R .; Graver, JE; Watkins, ME (1971), "The groups of the generalized Petersen graphs", Proceedings of the Cambridge Philosophical Society , 70 : 211-218, doi : 10.1017 / S0305004100049811.
- ^ 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 CS1 maint: parámetro desalentado ( enlace ).
- ^ Žitnik, Arjana; Horvat, Boris; Pisanski, Tomaž (2010), Todos los gráficos de Petersen generalizados son gráficos de unidad de distancia (PDF) , preimpresiones de IMFM, 1109.
- ^ Foster, RM (1932), "Circuitos geométricos de redes eléctricas", Transactions of the American Institute of Electrical Engineers , 51 : 309–317, doi : 10.1109 / T-AIEE.1932.5056068 CS1 maint: parámetro desalentado ( enlace ).
- ^ Bouwer, IZ; Chernoff, WW; Monson, B .; Star, Z (1988), The Foster Census , Centro de Investigación Charles Babbage.
- ^ Coxeter, HSM (1950), "Configuraciones auto-duales y gráficos regulares", Boletín de la American Mathematical Society , 56 : 413–455, doi : 10.1090 / S0002-9904-1950-09407-5 CS1 maint: parámetro desalentado ( enlace ).
- ^ Zacharias, M. (1941), "Untersuchungen über ebene Konfigurationen (124, 163)", Deutsche Mathematik , 6 : 147-170.
- ^ Pegg, Ed (2003), Gráficos simétricos cúbicos , Asociación Matemática de América CS1 maint: parámetro desalentado ( enlace ).