Gráfico de Nauru

En el campo matemático de la teoría de grafos , el grafo de Nauru es un grafo cúbico , bipartito y simétrico con 24 vértices y 36 aristas. Fue nombrado por David Eppstein en honor a la estrella de doce puntas de la bandera de Nauru . ^{[ 1 ]}

Tiene número cromático 2, índice cromático 3, diámetro 4, radio 4 y circunferencia 6. ^{[ 2 ]} También es un grafo 3 -conectado por vértices y 3 -conectado por aristas . Tiene grosor de libro 3 y número de cola 2. ^{[ 3 ]}

El grafo de Nauru requiere al menos ocho cruces en cualquier representación del mismo en el plano. Es uno de los tres grafos no isomorfos que comparten el título de ser el grafo cúbico más pequeño que requiere ocho cruces. Otro de estos tres grafos es el grafo de McGee , también conocido como la jaula (3-7) . ^{[ 4 ] [ 5 ]}

El grafo de Nauru es hamiltoniano y puede describirse mediante la notación LCF  : [5, − 9, 7, − 7, 9, − 5] ⁴ . ^{[ 1 ]}     

El grafo de Nauru también se puede construir como el grafo 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 que están a cinco pasos de distancia de él.

También existe una construcción combinatoria del grafo de Nauru. Se toman tres objetos distinguibles y se colocan en cuatro cajas distinguibles, con no más de un objeto por caja. Hay 24 maneras 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 de su ubicación actual a una caja vacía, entonces los vértices correspondientes a los dos estados se unen mediante una arista. El grafo de transición de estados resultante es el grafo de Nauru. En otras palabras, es el grafo de disposición.${\displaystyle A_{4,3}}$.

El grupo de automorfismos del grafo de Nauru es un grupo de orden 144. ^{[ 6 ]} Es isomorfo al producto directo de los grupos simétricos S ₄ y S ₃ y actúa transitivamente sobre los vértices, las aristas y los arcos del grafo. Por lo tanto, el grafo de Nauru es un grafo simétrico (aunque no transitivo en distancia ). Posee automorfismos que transforman cualquier vértice en cualquier otro vértice y cualquier arista en cualquier otra arista. Según el censo de Foster , el grafo de Nauru es el único grafo cúbico simétrico con 24 vértices. ^{[ 2 ]}

El grafo de Petersen generalizado G ( n,k ) es transitivo por vértices si y solo si n  =  10 y k  = 2 o si k² ≡ ±1 (mod n ) y es transitivo por aristas solo en los siguientes siete casos: ( n,k ) = (4,1), (5,2), (8,3), (10,2), (10,3), ⁽ 12,5), (24,5). ^{[ 7 ]} Por lo tanto, el grafo de Nauru es uno de los siete únicos grafos de Petersen generalizados simétricos. Entre estos siete grafos se encuentra el grafo cúbico.   ${\displaystyle G(4,1)}$, el gráfico de Petersen${\displaystyle G(5,2)}$, el gráfico de Möbius-Kantor${\displaystyle G(8,3)}$, el grafo dodecaédrico${\displaystyle G(10,2)}$y el gráfico de Desargues${\displaystyle 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).

Utilizando las permutaciones con signo de (1,1,3) como vértices, el grafo de Nauru se obtiene uniendo pares a una distancia euclidiana de 6.

El polinomio característico del grafo de Nauru es igual a

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

lo que la convierte en una gráfica integral , una gráfica cuyo espectro se compone enteramente de números enteros.

El grafo de Nauru tiene dos incrustaciones diferentes como un poliedro regular generalizado : una superficie topológica particionada en aristas, vértices y caras de tal manera que existe una simetría que toma cualquier bandera (una tripleta 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 grafo de Nauru es un grafo toroidal : consta de 12 caras hexagonales junto con los 24 vértices y 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 género 4. Su dual no es un grafo simple , puesto 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 por un haz 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.

Como todos los grafos de Petersen generalizados, el grafo de Nauru puede representarse mediante puntos en el plano de tal manera que los vértices adyacentes estén a una distancia unitaria; es decir, es un grafo de distancia unitaria . ^{[ 9 ]} Este y los prismas son 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 de grafo de distancia unitaria tiene el grupo diedral Dih ₆ como su grupo de simetría.

La primera persona en escribir sobre el grafo de Nauru fue RM Foster , en un esfuerzo por recopilar todos los grafos cúbicos simétricos. ^{[ 10 ]} La lista completa de grafos cúbicos simétricos ahora lleva su nombre, el Censo de Foster , y dentro de esta lista el grafo de Nauru está numerado como grafo F24A, pero no tiene un nombre específico. ^{[ 11 ]} En 1950, HSM 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. ^{[ 12 ] [ 13 ]}

En 2003, Ed Pegg escribió en su columna en línea de MAA que F24A merecía un nombre, pero no propuso ninguno. ^{[ 14 ]} Finalmente, en 2007, David Eppstein utilizó el nombre de grafo 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 grafo como un grafo de Petersen generalizado. ^{[ 1 ]}