Grafo de Nauru
# Grafo de Nauru

No campo da matemática da teoria dos grafos o grafo de Nauru é um grafo simétrico, bipartido cúbico com 24 vértices e 36 arestas. Foi nomeado por David Eppstein em alusão a estrela de doze pontas da bandeira do Nauru
Ele tem número cromático 2, índice cromático 3, raio 4, diâmetro 4, e cintura 6. Ele também é 3-vértice-conectado, e 3-aresta-conectado.
Os menores grafos cúbicos com número de cruzamento entre 1 e 8 são conhecidos (sequência A110507 na OEIS). O menor grafo com 8 cruzamentos é o grafo de Nauru. Existe 5 grafos cúbicos não-isomorfos de ordem 24 com número de cruzamentos de 8. Um deles é o grafo de McGee também conhecido como (3-7)-gaiola.

## Construção

O grafo de Nauru é Hamiltoniano e pode ser descrito pela notação LCF : [5, −9, 7, −7, 9, −5]$^4$.
O grafo de Nauru também pode ser construído como o grafo de Petersen generalizado G(12, 5) que é formado pelos vértices de um dodecágono, ligado aos vértices de uma estrela de doze pontos, em que cada ponta da estrela está ligada aos pontos quer estão a cinco passos de distância dela.

## Propriedades algébricas

O grupo de automorfismo do grafo de Nauru é um grupo de ordem 144. É isomórfico ao produto direto dos grupos simétricos S$_4$ e S$_3$ e age transitivamente nos vértices, nas arestas e nos arcos do grafo. Portanto o grafo de Nauru é um grafo simétrico (embora não seja distância-transitivo). Ele tem automorfismos que levam qualquer vértice para qualquer outro vértice e qualquer aresta para qualquer outra aresta. De acordo com o censo de Foster, o grafo de Nauru é o único grafo cúbico simétrico em 24 vértices.
O grafo generalizado de Petersen G(n,k) é vértice-transitivo se e somente se n = 10 e k =2 ou se k$^2$ ≡ ±1 (mod n) e é aresta-transitivo somente nos sete casos seguintes: (n,k) = (4,1), (5,2), (8,3), (10,2), (10,3), (12,5), (24,5). Assim, o grafo de Nauru é um de apenas sete grafos simétricos generalizados de Petersen. Entre estes sete grafos estão o grafo cubico $G(4,1)$, o grafo de Petersen $G(5,2)$, o grafo de Möbius–Kantor $G(8,3)$, o grafo dodecaedro $G(10,2)$ e o grafo de Desargues $G(10,3)$.
O grafo de Nauru é um grafo de Cayley de S$_4$, o grupo de permutações simétricas em quatro elementos, gerados pelas três maneiras diferentes de trocar o primeiro elemento com um dos outros três: (1 2), (1 3) e (1 4).
O polinômio característico do grafo de Nauru é igual a
    $(x-3)(x-2)^{6}(x-1)^{3}x^{4}(x+1)^{3}(x+2)^{6}(x+3),\$
tornando-o um grafo integral—um grafo cujo espectro consiste inteiramente de inteiros.
| Toro simétrico incorporado O toro é formado, topologicamente, colando-se arestas opostas de um hexágono regular com o outro. | Grafo de Petersen generalizado As cores e permutações indicam, que este é um grafo de Cayley de S$_4$. | Matriz de adjacência Cada aresta é representada por duas entradas na mesma cor, que são simétricas à diagonal principal. |

## Propriedades topológicas

O grafo de Nauru tem duas incorporções diferentes como poliedros regulares generalizados:
superfícies topológicas particionadas em arestas, vértices e faces de tal forma que há uma simetria levando qualquer bandeira (uma tripla incidente de um vértice, uma aresta e uma face) em qualquer outra bandeira.
Uma destas duas incorporações forma um toro, de modo que o grafo de Nauru é um grafo toroidal: consiste de 12 faces hexagonais, juntamente com os 24 vértices e 36 arestas do grafo de Nauru. O grafo dual desta incorporação é um grafo simétrico 6-regular com 12 vértices e 36 arestas.
A outra incorporação simétrica do gráfico Nauru tem seis faces dodecagonais, e formas de uma superfície de gênero 4. Seu dual não é um grafo simples, uma vez que cada face compartilha três arestas com quatro outras faces, mas um multigrafo. Este dual pode ser formado a partir do grafo de um octaedro regular substituindo cada aresta por um feixe de três arestas paralelas.
O conjunto de faces de qualquer um destas duas incorporações é o conjunto de polígonos de Petrie da outra incorporação.

## Propriedades geométricas

Tal como acontece com todos os grafos generalizados de Petersen, o grafo de Nauru pode ser representado por pontos no plano de tal forma que os vértices adjacentes estão em unidade de distância à parte; isto é, ele é um grafo distancia-unidade. Ele e os prismas são os únicos grafos generalizados de Petersen G(n,p) que não pode ser representado de tal forma que as simetrias do desenho formam um grupo cíclico de ordem n. Em vez disso, a representação de seu grafo distancia-unidade tem o grupo diedral Dih$_6$ como o seu grupo de simetria.

## História

A primeira pessoa a escrever sobre o gráfico Nauru foi R. M. Foster em um eforço para colecionar todos os grafos cúbicos simétricos.. Toda a lista de grafos simétricos cúbicos agora é nomeada depois dele como Foster Census e dentro desta lista, o gráfico de Nauru é numerado como o gráfico F24A, mas não possui um nome específico. Em 1950, H. S. M. Coxeter citou o gráfico uma segunda vez, dando a representação hamiltoniana usada para ilustrar este artigo e descrevendo-o como o grafo de Levi de uma configuração projetiva descoberta por Zacharias.
Em 2003, Ed Pegg escreveu em sua coluna on-line do MAA que F24A merecia um nome, mas não propôs um. Finalmente, em 2007, David Eppstein usou o nome Grafo de Nauru devido ao fato da bandeira da República de Nauru tem uma estrela de 12 pontos semelhante à que aparece na construção do gráfico como um gráfico generalizado de Petersen.