Grafo de Papo

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]

Grafo de Papo
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

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: ${\displaystyle (x-1)x(x^{16}-26x^{15}+325x^{14}-2600x^{13}+14950x^{12}-65762x^{11}+}$${\displaystyle 229852x^{10}-653966x^{9}+1537363x^{8}-3008720x^{7}+4904386x^{6}-}$${\displaystyle 6609926x^{5}+7238770x^{4}-6236975x^{3}+3989074x^{2}-1690406x+356509)}$.

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

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 é: ${\displaystyle (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

• 
  Grafo de Papo colorido para destacar vários ciclos.
• 
  O índice cromático do grafo de Papo é 3.
• 
  O número cromático do grafo de Papo é 2.

Referências

1. Weisstein, Eric W. «Pappus Graph». MathWorld (em inglês)
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.