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. É 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.Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.
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 , 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.Royle, G. "Cubic Symmetric Graphs (The Foster Census)." Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.
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.
Galeria
Categoria:Grafos regulares Categoria:Grafos individuais Categoria:Papo de Alexandria