Grafo de Nauru

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Translation Latin Alphabet.svg
Este artigo ou secção está a ser traduzido. Ajude e colabore com a tradução.
Grafo de Nauru
Nauru graph.svg

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 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 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

(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 S4.
Matriz de adjacência
Cada aresta é representada por duas entradas na mesma cor, que são simétricas à diagonal principal.

Propriedades topológicas[editar | editar código-fonte]

Uma incorporação simétrica do grafo de Nauru sobre uma superfície de gênero-4, com seis faces dodecagonais.

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]

O grafo de Nauru como um grafo unidade de distância, em Žitnik, Horvat & Pisanski (2010).

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]


Referências

  1. a b Eppstein, D., The many faces of the Nauru graph on LiveJournal, 2007.
  2. a b Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.
  3. PEGG, E. T.; EXOO, G.. ({{{mês}}} 2009). "Crossing number graphs". Mathematica Journal 11..
  4. Eric W. Weisstein, Graph Crossing Number em MathWorld
  5. Royle, G. F024A data
  6. Frucht, R.; Graver, J. E.; Watkins, M. E.. ({{{mês}}} 1971). "The groups of the generalized Petersen graphs". Proceedings of the Cambridge Philosophical Society 70 p. 211–218. DOI:10.1017/S0305004100049811.
  7. McMullen, Peter (1992), "The regular polyhedra of type {p, 3} with 2p vertices", Geometriae Dedicata 43 (3): 285–289, doi:10.1007/BF00151518 .
  8. Žitnik, Arjana; Horvat, Boris; Pisanski, Tomaž (2010), All generalized Petersen graphs are unit-distance graphs, IMFM preprints, 1109, http://www.imfm.si/preprinti/PDF/01109.pdf .
  9. Foster, R. M. ({{{mês}}} 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..