Grafo de Papo

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

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

↑ Weisstein, Eric W. «Pappus Graph». MathWorld (em inglês)
↑ Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.
↑ 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
↑ Royle, G. "Cubic Symmetric Graphs (The Foster Census)." Arquivado em 20 de julho de 2008, no Wayback Machine.
↑ Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.

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

[1]

[2]

[3]

[4]

[5]