Grafo de Nauru
| Grafo de Nauru | |
|---|---|
 O grafo Nauru | |
| vértices | 24 |
| arestas | 36 |
| Raio | 4 |
| Diâmetro | 4 |
| Cintura | 6 |
| Automorfismos | 144 (S4×S3) |
| Número cromático | 2 |
| Índice cromático | 3 |
| Propriedades | Cúbico Hamiltoniano simétrico Integral Bipartido Grafo de Cayley |
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[1]
Ele tem número cromático 2, índice cromático 3, raio 4, diâmetro 4, e cintura 6[2]. 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[3]. Um deles é o grafo de McGee também conhecido como (3-7)-gaiola[4].
Construção
[editar | editar código-fonte]O grafo de Nauru é Hamiltoniano e pode ser descrito pela notação LCF : [5, −9, 7, −7, 9, −5]4.[1]
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
[editar | editar código-fonte]O grupo de automorfismo do grafo de Nauru é um grupo de ordem 144[5]. É isomórfico ao produto direto dos grupos simétricos S4 e S3 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[2].
O grafo generalizado de Petersen G(n,k) é vértice-transitivo se e somente se n = 10 e k =2 ou se k2 ≡ ±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)[6]. Assim, o grafo de Nauru é um de apenas sete grafos simétricos generalizados de Petersen. Entre estes sete grafos estão o grafo cubico , o grafo de Petersen , o grafo de Möbius–Kantor , o grafo dodecaedro e o grafo de Desargues .
O grafo de Nauru é um grafo de Cayley de S4, 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
tornando-o um grafo integral—um grafo cujo espectro consiste inteiramente de inteiros.
.svg) O toro é formado, topologicamente, colando-se arestas opostas de um hexágono regular com o outro. |
.svg) As cores e permutações indicam, que este é um grafo de Cayley de S4. |
.svg) Cada aresta é representada por duas entradas na mesma cor, que são simétricas à diagonal principal. |
Propriedades topológicas
[editar | editar código-fonte]
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[7].
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
[editar | editar código-fonte]
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.[8] 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 Dih6 como o seu grupo de simetria.
História
[editar | editar código-fonte]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..[9] 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.[10] 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.[11][12]
Em 2003, Ed Pegg escreveu em sua coluna on-line do MAA que F24A merecia um nome, mas não propôs um.[13] 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.[1]
Referências
- ↑ a b c Eppstein, D., The many faces of the Nauru graph Arquivado em 21 de julho de 2011, no Wayback Machine. on LiveJournal, 2007.
- ↑ a b Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.
- ↑ PEGG, E. T.; EXOO, G. (2009). «Crossing number graphs». Mathematica Journal. 11.
- ↑ Weisstein, Eric W. «Graph Crossing Number». MathWorld (em inglês)
- ↑ Royle, G. F024A data[ligação inativa]
- ↑ Frucht, R.; Graver, J. E.; Watkins, M. E. (1971). «The groups of the generalized Petersen graphs». Proceedings of the Cambridge Philosophical Society. 70. p. 211–218. doi:10.1017/S0305004100049811
- ↑ McMullen, Peter (1992), «The regular polyhedra of type {p, 3} with 2p vertices», Geometriae Dedicata, 43 (3): 285–289, doi:10.1007/BF00151518.
- ↑ Žitnik, Arjana; Horvat, Boris; Pisanski, Tomaž (2010), All generalized Petersen graphs are unit-distance graphs (PDF), IMFM preprints, 1109.
- ↑ Foster, R. M. (1932). «Geometrical circuits of electrical networks». Transactions of the American Institute of Electrical Engineers. 51. p. 309–317. doi:10.1109/T-AIEE.1932.5056068.
- ↑ Bouwer, I. Z.; Chernoff, W. W.; Monson, B.; Star, Z (1988). «The Foster Census». Charles Babbage Research Centre .
- ↑ Coxeter, H. S. M. (1950). «Self-dual configurations and regular graphs». Bulletin of the American Mathematical Society. 56: 413–455. doi:10.1090/S0002-9904-1950-09407-5.
- ↑ Zacharias, M. (1941). «Untersuchungen über ebene Konfigurationen (124, 163)». Deutsche Mathematik. 6: 147–170.
- ↑ Pegg, Ed (2003). «Cubic Symmetric Graphs». Mathematical Association of America.