Abrir menu principal

Grafo de Papo

(Redirecionado de Grafo de Pappus)
Grafo de Papo
Pappus graph LS.svg
Grafo de Papo
Nomeado em honra a Papo 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 Papo é um grafo não-orientado 3-regular com 18 vértices e 27 arestas formado como o grafo de Levi da configuração de Papo.[1] É nomeado em honra a Papo de Alexandria, um antigo matemático grego que se acredita ter descoberto o "teorema do hexágono" que descreve a configuração de Papo. Todos os grafos distância-regular cúbicos são conhecidos; o grafo de Papo é um destes 13 grafos.[2]

O grafo de Papo 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 Papo tem um polinômio cromático igual a: .

O nome "grafo de Papo" 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 Papo 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ébricasEditar

O grupo de automorfismo do grafo de Papo é um grupo de ordem 216. Ele age transitivamente sobre os vértices, nas arestas e nos arcos do grafo. Portanto, o grafo de Papo é um 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 Papo é:  . É o único grafo com este polinômio característico, tornando-se um grafo determinado pelo seu espectro.

GaleriaEditar

Referências

  1. Weisstein, Eric W. «Pappus Graph» (em inglês). 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», The Johns Hopkins University Press, American Journal of Mathematics, 69 (4): 859–863, doi:10.2307/2371806 
  4. Royle, G. "Cubic Symmetric Graphs (The Foster Census)." Arquivado em 20 de julho de 2008, no Wayback Machine.
  5. Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.