Grafo de Pappus

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Grafo de Pappus
Pappus graph LS.svg

O grafo de Pappus
Nomeado em honra a Pappus de Alexandria
vértices 18
arestas 27
Raio 4
Diâmetro 4
Cintura 6
Automorfismos 216
Número cromático 2
Índice cromático 3
Propriedades Cúbico
Hamiltoniano
Simétrico
Distância-transitivo
Distância-regular

No campo da matemática da teoria dos grafos o grafo de Pappus é um grafo não-orientado 3-regular com 18 vértices e 27 arestas formado como o grafo de Levi da configuração de Pappus.1 É nomeado em honra a Pappus de Alexandria, um antigo matemático grego que se acredita ter descoberto o "teorema do hexágono" que descreve a configuração de Pappus. Todos os grafos distância-regular cúbicos são conhecidos; o grafo de Pappus é um destes 13 grafos.2

O grafo de Pappus tem um número de cruzamento retilíneo 5, e é o menor grafo cúbico com este número de cruzamento. Tem cintura 6, diâmetro 4, raio 4, número cromático 2, índice cromático 3 e é tanto 3-vértice-conectado quanto 3-aresta-conectado.

O grafo de Pappus tem um polinômio cromático igual a: (x-1)x(x^{16}-26x^{15}+325x^{14}-2600x^{13}+14950x^{12}-65762x^{11}+229852x^{10}-653966x^9+1537363x^8-3008720x^7+4904386x^6-6609926x^5+7238770x^4-6236975x^3+3989074x^2-1690406x+356509).

O nome "grafo de Pappus" também tem sido usado para se referir a um grafo relacionado com nove vértices 3 , com um vértice para cada ponto da configuração de Pappus e uma aresta para cada par de pontos na mesma linha; este grafo de nove vértice é 6-regular, e é o grafo complementar da união de três grafos triângulo disjuntos.

Propriedades algébricas[editar | editar código-fonte]

O grupo de automorfismo do grafo de Pappus é um grupo de ordem 216. Ele age transitivamente sobre os vértices, nas arestas e nos arcos do grafo. Portanto, o grafo de Pappus é im grafo simétrico. 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 Biggs-Smith, referenciado como F018A, é o único grafo cúbico simétrico em 18 vértices.4 5

O polinômio característico do grafo de Pappus é: (x-3) x^4 (x+3) (x^2-3)^6. É o único grafo com este polinômio característico, tornando-se um grafo determinado pelo seu espectro.

Galeria[editar | editar código-fonte]

Referências

  1. Eric W. Weisstein, Pappus Graph em MathWorld
  2. Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.
  3. Kagno, I. N. (1947), "Desargues' and Pappus' graphs and their groups", American Journal of Mathematics (The Johns Hopkins University Press) 69 (4): 859–863, doi:10.2307/2371806, http://jstor.org/stable/2371806 
  4. Royle, G. "Cubic Symmetric Graphs (The Foster Census)."
  5. Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.