Summary
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]
| 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 | |
Propiedades generales
editarEl 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:
- .
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 K3,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í.
Propiedades algebraicas
editarEl 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 . Es el único con este polinomio característico, por lo que es un grafo determinado por su espectro.
Galería
editar-
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
Referencias
editar- ↑ Weisstein, Eric W. «Pappus Graph». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
- ↑ Brouwer, A. E.; Cohen, A. M.; and Neumaier, A. Distance-Regular Graphs. New York: Springer-Verlag, 1989.
- ↑ Jessica Wolz, Engineering Linear Layouts with SAT. Master Thesis, University of Tübingen, 2018
- ↑ Kagno, I. N. (1947), «Desargues' and Pappus' graphs and their groups», American Journal of Mathematics (The Johns Hopkins University Press) 69 (4): 859-863, JSTOR 2371806, doi:10.2307/2371806.
- ↑ Royle, G. "Cubic Symmetric Graphs (The Foster Census)." Archivado el 12 de septiembre de 2015 en Wayback Machine.
- ↑ Conder, M. and Dobcsányi, P. "Trivalent Symmetric Graphs Up to 768 Vertices." J. Combin. Math. Combin. Comput. 40, 41-63, 2002.
Datos: Q3115526
Multimedia: Pappus graph / Q3115526
