Grafo de Nauru

Grafo de Nauru
Vértices	24
Aristas	36
Radio	4
Diámetro	4
Cintura	6
Automorfismos	144 (S4×S3)
Número cromático	2
Índice cromático	3
Propiedades	Simétrico Cúbico Hamiltoniano Integral Grafo de Cayley Bipartito

En el campo matemático de la teoría de grafos, el grafo de Nauru es un grafo cúbico bipartito y simétrico, que cuenta con 24 vértices y 36 aristas. Fue nombrado por David Eppstein haciendo referencia a la estrella de doce puntas que figura en la bandera de Nauru.​

Tiene coloración de grafos 2, índice cromático 3, diámetro 4, radio 4 y cintura 6.​ También es un grafo 3-vértices-conectado y 3-aristas-conectado. Tiene embebido en libro 3 y número de cola 2.​

El grafo de Nauru requiere al menos ocho cruces en cualquier dibujo del mismo en el plano. Es uno de los cinco grafos no isomorfos caracterizados por ser los grafos cúbicos más pequeños que requieren ocho cruces. Otro de estos cinco grafos es el grafo de McGee, también conocido como (3-7)-jaula.​​

Construcción

El grafo de Nauru es hamiltoniano y se puede describir mediante la notación LCF como: [5, −9, 7, −7, 9, −5]⁴.​

El grafo de Nauru también se puede construir como el grafo generalizado de Petersen G(12, 5) que está formado por los vértices de un dodecágono conectado a los vértices de una estrella de doce puntas en la que cada punta de la estrella está conectada a los puntos situados a cinco pasos de ella.

También hay una construcción combinatoria del grafo de Nauru. Se obtiene tomando tres objetos distinguibles y colocándolos 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 grafo. 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 grafo de transición de estado resultante es el grafo de Nauru.

Propiedades algebraicas

El grupo de automorfismos del grafo de Nauru es un grupo de orden 144.​ Es isomorfo al producto directo de los grupos simétricos S₄ y S₃ y actúa transitivamente sobre los vértices, sobre las aristas y sobre los arcos del grafo. Por lo tanto, el grafo de Nauru es un grafo simétrico (aunque no distancia transitivo). Posee 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 Nauru es el único grafo simétrico cúbico en 24 vértices.​

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), (24,5).​ Entonces, el grafo de Nauru es uno de los siete grafos de Petersen generalizados simétricos. Entre estos siete grafos se encuentran el grafo cúbico $G(4,1)$, el grafo de Petersen $G(5,2)$, el grafo de Möbius-Kantor $G(8,3)$, el grafo dodecaédrico $G(10,2)$ y el grafo de Desargues $G(10,3)$.

El grafo de Nauru es un grafo de Cayley de S₄, 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 grafo de Nauru es igual a:

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

convirtiéndolo en un grafo integral, un grafo cuyo espectro consiste completamente en números enteros.

Incrustación simétrica en un toro formado por pegado de aristas opuestas de un hexágono regular Incrustación simétrica en un toro formado por pegado de aristas opuestas de un hexágono regular   Grafo generalizado de Petersen, coloreado y etiquetado como un gráfico de Cayley de S4 Grafo generalizado de Petersen, coloreado y etiquetado como un gráfico de Cayley de S4   Matriz de adyacencia. Cada arista está representada por dos entradas colocadas simétricamente en el mismo color Matriz de adyacencia. Cada arista está representada por dos entradas colocadas simétricamente en el mismo color   Grafo 1-planar con 8 cruces Grafo 1-planar con 8 cruces   24 orientaciones de un octaedro rodante en un teselado triangular, dibujado en un toro hexagonal 24 orientaciones de un octaedro rodante en un teselado triangular, dibujado en un toro hexagonal

Propiedades topológicas

Un embebido simétrico del gráfico de Nauru en una superficie de género 4, con seis caras dodecagonales

El grafo de Nauru tiene dos embebidos diferentes como poliedro regular generalizado: una superficie topológica dividida en aristas, vértices y caras de tal manera que existe una simetría que toma cualquier bandera (una triple incidencia de un vértice, una arista y una cara) en cualquier otra bandera.​

Una de estas dos incrustaciones forma un toro, por lo que el grafo de Nauru es un grafo toroidal: consta de 12 caras hexagonales junto con los 24 vértices y las 36 aristas del grafo de Nauru. El grafo dual de esta incrustación es un grafo simétrico 6-regular con 12 vértices y 36 aristas.

La otra incrustación simétrica del grafo de Nauru tiene seis caras dodecagonales y forma una superficie de genus 4. Su dual no es un grafo, ya que cada cara comparte tres aristas con otras cuatro caras, sino un multigrafo. Este dual se puede formar a partir del grafo de un octaedro regular reemplazando cada arista con un paquete de tres aristas paralelas.

El conjunto de caras de cualquiera de estas dos incrustaciones es el conjunto de los polígonos de Petrie del otro embebido.

Propiedades geométricas

El grafo de Nauru como un grafo de distancia unitaria, procedente de Žitnik, Horvat y Pisanski (2010)

Al igual que con todos los grafos de Petersen generalizados, el grafo 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 un grafo de distancia unitaria,​ siendo los prismas los únicos grafos 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 diedro Dih₆ como su grupo de simetría.

Historia

Bandera de Nauru, con su estrella de doce puntas

La primera persona en escribir sobre el grafo de Nauru fue R. M. Foster, durante su trabajo para recopilar todos los grafos simétricos cúbicos.​ La lista completa de grafos simétricos cúbicos ahora lleva su nombre Censo de Foster y dentro de esta lista, el grafo de Nauru está numerado como grafo F24A, y no tiene un nombre específico.​ En 1950, Harold Scott MacDonald Coxeter citó el grafo por segunda vez, dando la representación hamiltoniana utilizada para ilustrar este artículo y describiéndolo como el grafo de Levi de una configuración proyectiva descubierta por Zacharias.​​

En 2003, Ed Pegg escribió en su columna MAA en línea que F24A merecía un nombre propio, pero no lo propuso.​ Finalmente, en 2007, David Eppstein usó el nombre de grafo de Nauru porque la bandera de Nauru contiene una estrella de 12 puntas similar a la que aparece en la construcción del grafo como un grafo de Petersen generalizado.​

Referencias

• Datos: Q3115524
• Multimedia: Nauru graph / Q3115524