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 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. Todos los cúbicos gráficos distancia regular son conocidos; el gráfico de Pappus es uno de los 13 gráficos de este tipo. [2]
Gráfico de Pappus | |
---|---|
Lleva el nombre de | Pappus de Alejandría |
Vértices | 18 |
Bordes | 27 |
Radio | 4 |
Diámetro | 4 |
Circunferencia | 6 |
Automorfismos | 216 |
Número cromático | 2 |
Índice cromático | 3 |
Espesor del libro | 3 |
Número de cola | 2 |
Propiedades | Hamiltoniano cúbico bipartito simétrico distancia-transitivo distancia-regular |
Tabla de gráficos y parámetros |
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 bordes . Tiene un grosor de libro 3 y un número de cola 2. [3]
El gráfico de Pappus tiene un polinomio cromático igual a:.
El nombre "gráfico de Pappus" también se ha utilizado para referirse a un gráfico de nueve vértices relacionado, [4] con un vértice para cada punto de la configuración de Pappus y un borde para cada par de puntos en la misma línea; este gráfico de nueve vértices es 6-regular, es el gráfico de complemento de la unión de tres gráficos de triángulos disjuntos y es el gráfico tripartito completo K 3,3,3 . El primer gráfico 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í.
Propiedades algebraicas
El grupo de automorfismos del grafo de Pappus es un grupo de orden 216. Actúa de forma transitiva sobre los vértices, las aristas y los arcos del grafo. Por lo tanto, el gráfico de Pappus es un gráfico simétrico . Tiene automorfismos que llevan cualquier vértice a cualquier otro vértice y cualquier borde a cualquier otro borde. 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 en 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, lo que lo convierte en un gráfico determinado por su espectro.
Galería
Gráfico de Pappus coloreado para resaltar varios ciclos.
El índice cromático del gráfico de Pappus es 3.
El número cromático del gráfico de Pappus es 2.
El gráfico de Pappus incrustado en el toro, como un mapa regular con nueve caras hexagonales.
El gráfico de Pappus y el mapa asociado incrustados en el toro.
Referencias
- ^ Weisstein, Eric W. "Gráfico de Pappus" . MathWorld .
- ^ Brouwer, AE; Cohen, AM; y Neumaier, A. Gráficos regulares de distancia. Nueva York: Springer-Verlag, 1989.
- ^ Jessica Wolz, Diseños lineales de ingeniería con SAT. Tesis de maestría, Universidad de Tübingen, 2018
- ^ 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
- ^ Royle, G. "Gráficos simétricos cúbicos (el censo de Foster)".
- ^ Conder, M. y Dobcsányi, P. "Gráficos simétricos trivalentes hasta 768 vértices". J. Combin. Matemáticas. Combin. Computación. 40, 41-63, 2002.