Grafo de Papo , la enciclopedia libre

Grafo de Papo
El grafo de Papo
Nombre en honor a	Papo de Alejandría
Vértices	18
Radio	4
Diámetro	4
Cintura	6
Automorfismos	216
Número cromático	2
Índice cromático	3
Propiedades	Bipartito Simétrico Distancia-transitivo Distancia-regular Cúbico Hamiltoniano
[editar datos en Wikidata]

En el campo matemático de la teoría de grafos, el grafo de Papo (también conocido como grafo de Pappus) es un grafo 3-regular bipartito con 18 vértices y 27 aristas, que se obtiene generando el grafo de Levi de la configuración de Papo.^[1]​ Lleva el nombre de Papo de Alejandría, un matemático de la antigua Grecia que se cree que descubrió el teorema del hexágono, una proposición geométrica en la que se describe la denominada configuración de Papo. Se conocen todos los grafos de distancia regular cúbicos, y el grafo de Papo es uno de los 13 grafos de este tipo.^[2]​

El grafo de Papo tiene un número de cruce rectilíneo 5 y es el grafo cúbico más pequeñ o con ese número de cruce (sucesión A110507 en OEIS). Tiene cintura 6, diámetro 4, radio 4, coloración de grafos 2, índice cromático 3 y es tanto 3-vértices-conectado como 3-aristas-conectado. Tiene embebido en libro 3 y número de cola 2.^[3]​

Posee un polinomio 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)}$.

El término grafo de Papo también se ha utilizado para referirse a un grafo de nueve vértices^[4]​ que tiene un vértice por cada punto de la configuración de Papo y una arista por cada par de puntos en la misma recta. Este grafo de nueve vértices es 6-regular; es el grafo complemento de la unión de tres grafos triangulares disjuntos; y es el grafo tripartito completo K_3,3,3. El primer grafo de Papo se puede embeber en un toro para formar un mapa regular autodual de Petrie con nueve caras hexagonales; y el segundo para formar un mapa regular con 18 caras triangulares. Los dos mapas toroidales regulares son duales entre sí.

El grupo de automorfismos del grafo de Papo es un grupo de orden 216. Actúa transitivamente sobre los vértices, sobre las aristas y sobre los arcos del grafo. Por lo tanto, es un grafo simétrico. Tiene automorfismos que llevan cualquier vértice a cualquier otro vértice y cualquier arista a cualquier otra arista. Según la recopilación de Foster, el grafo de Pappus, denominado F018A, es el único grafo simétrico cúbico de 18 vértices.^[5]​^[6]​

El polinomio característico del grafo de Papo es ${\displaystyle (x-3)x^{4}(x+3)(x^{2}-3)^{6}}$. Es el único con este polinomio característico, por lo que es un grafo determinado por su espectro.

• 
  Grafo de Papo coloreado para resaltar varios ciclos
• 
  El índice cromático del grafo de Papo es 3
• 
  La coloración de grafos del grafo de Papo es 2
• 
  El grafo de Papo embebido en el toro, como una distribución regular con nueve caras hexagonales
• 
  El grafo de Papo y su distribución asociada embebidos en el toro