Gráfico de Pappus

Gráfico bipartito no dirigido de 3 regulares

En el campo matemático de la teoría de grafos , el gráfico de Pappus es un gráfico bipartito , 3 regulares y no dirigido con 18 vértices y 27 aristas, formado como el gráfico de Levi de la configuración de Pappus . ^[1] Lleva el 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 todas las gráficas cúbicas y regulares en distancias ; el gráfico de Pappus es uno de los 13 de este tipo. ^[2]

El gráfico de Pappus tiene un número de cruce rectilíneo 5 y es el gráfico cúbico más pequeño con ese número de cruce (secuencia A110507 en la OEIS ). Tiene circunferencia 6, diámetro 4, radio 4, número cromático 2, índice cromático 3 y está conectado por 3 vértices y por 3 aristas . Tiene un grosor de libro 3 y una cola número 2. ^[3]

La gráfica de Pappus tiene un polinomio cromático igual a:

$${\displaystyle (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)}$$

El nombre "gráfico de Pappus" también se ha utilizado para referirse a un gráfico relacionado de nueve vértices, ^[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; esta gráfica de nueve vértices es 6-regular, es la gráfica complementaria de la unión de tres gráficas triangulares disjuntas y es la gráfica tripartita completa K _3,3,3 . El primer gráfico de Pappus se puede incrustar en el toro para formar un mapa regular dual de Petrie con nueve caras hexagonales; el segundo, formar un mapa regular con 18 caras triangulares. Los dos mapas toroidales regulares son duales entre sí.

Propiedades algebraicas

El grupo de automorfismos del grafo de Pappus es un grupo de orden 216. Actúa transitivamente sobre los vértices, las aristas y los arcos del grafo. Por tanto, la gráfica de Pappus es una gráfica simétrica . 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 gráfico de Pappus, al que se hace referencia como F018A, es el único gráfico simétrico cúbico de 18 vértices. ^{[5] [6]}

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

Galería

• 
  Gráfico de Pappus coloreado para resaltar varios ciclos.
• 
  El índice cromático del gráfico Pappus es 3.
• 
  El número cromático del gráfico de Pappus es 2.
• 
  El gráfico de Pappus incrustado en el toroide, como un mapa regular con nueve caras hexagonales.
• 
  El gráfico de Pappus y el mapa asociado incrustados en el toroide.

Referencias

1. Weisstein, Eric W. "Gráfico de Pappus". MundoMatemático .
2. Brouwer, AE; Cohen, AM; y Neumaier, A. Gráficos regulares de distancia. Nueva York: Springer-Verlag, 1989.
3. Jessica Wolz, Ingeniería de diseños lineales con SAT. Tesis de maestría, Universidad de Tübingen, 2018
4. Kagno, IN (1947), "Gráficos de Desargues y Pappus y sus grupos", American Journal of Mathematics , The Johns Hopkins University Press, 69 (4): 859–863, doi :10.2307/2371806, JSTOR  2371806
5. Royle, G. "Gráficos simétricos cúbicos (el censo de Foster)".
6. Conder, M. y Dobcsányi, P. "Gráficos simétricos trivalentes de hasta 768 vértices". J. Combinar. Matemáticas. Combinar. Computadora. 40, 41-63, 2002.