En el campo matemático de la teoría de grafos , el grafo de Pappus es un grafo bipartito , 3- regular , no dirigido, con 18 vértices y 27 aristas, formado como el grafo de Levi de la configuración de Pappus . [1] Recibe su nombre de Pappus de Alejandría , un antiguo matemático griego que se cree que descubrió el "teorema del hexágono" que describe la configuración de Pappus. Se conocen todos los grafos cúbicos , de distancia regular ; el grafo de Pappus es uno de los 13 grafos de este tipo. [2]
El grafo de Pappus tiene un número de cruce rectilíneo de 5 y es el grafo cúbico más pequeño con ese número de cruce (secuencia A110507 en la OEIS ). Tiene circunferencia de 6, diámetro de 4, radio de 4, número cromático de 2, índice cromático de 3 y está conectado por 3 vértices y por 3 aristas . Tiene un grosor de libro de 3 y un número de cola de 2. [3]
El gráfico de Pappus tiene un polinomio cromático igual a:
El nombre "grafo de Pappus" también se ha utilizado para referirse a un grafo de nueve vértices relacionado, [4] con un vértice para cada punto de la configuración de Pappus y una arista para cada par de puntos en la misma línea; este grafo de nueve vértices es 6-regular, es el grafo complementario de la unión de tres grafos triangulares disjuntos , y es el grafo tripartito completo K 3,3,3 . El primer grafo de Pappus se puede incrustar en el toro para formar un mapa regular dual auto-Petrie con nueve caras hexagonales; 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 Pappus 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 el grafo de Pappus 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 el censo de Foster , el grafo de Pappus, referenciado como F018A, es el único grafo cúbico simétrico sobre 18 vértices. [5] [6]
El polinomio característico del grafo de Pappus es . Es el único grafo con este polinomio característico, lo que lo convierte en un grafo determinado por su espectro.
