Grafo de Levi

Plantilla:Infobox graph En combinatorial mathematics, un gráfico de Levi o un gráfico de incidencia es un grafo bipartito asociado con un estructura de incidencia.​​ A partir de una colección de puntos y líneas en un geometría de incidencia o un projective configuration, formamos un gráfico con un vértice por punto, un vértice por línea y una arista para cada incidencia entre un punto y una línea. Llevan el nombre de Friedrich Wilhelm Levi, quien escribió sobre ellos en 1942.​​

La gráfica de Levi de un sistema de puntos y rectas generalmente tiene girth al menos seis: Cualquier 4-cycles correspondería a dos rectas que pasan por los mismos dos puntos. Por el contrario, cualquier gráfico bipartito con una circunferencia de al menos seis puede verse como el gráfico de Levi de una estructura de incidencia abstracta. Los gráficos de configuraciones​ de Levi son biregular, y cada gráfico biregular con una circunferencia de al menos seis puede verse como el gráfico de Levi de una configuración abstracta.​

Los gráficos de Levi también se pueden definir para otros tipos de estructura de incidencia, como las incidencias entre puntos y planos en Espacio euclídeo. Para cada gráfico de Levi, existe un hipergrafo equivalente y viceversa.

Ejemplos

Heawood graph and Fano plane
Vertex 3 is part of the circular edge (3, 5, 6), the diagonal edge (3, 7, 4), and the side edge (1, 3, 2).

• El Grafo de Desargues es el gráfico de Levi del Configuración de Desargues, compuesto por 10 puntos y 10 líneas. Hay 3 puntos en cada línea y 3 líneas que pasan por cada punto. El gráfico de Desargues también se puede ver como grafo de Petersen generalizado G(10,3) o bipartite Kneser graph con parámetros 5,2. Es 3-regular con 20 vértices.
• El Grafo de Heawood es el gráfico de Levi del Plano de Fano. También se conoce como (3,6) -cage y es 3-regular con 14 vértices.
• El Grafo de Möbius-Kantor es el gráfico de Levi del Möbius–Kantor configuration, un sistema de 8 puntos y 8 rectas que no se puede realizar mediante rectas en el plano euclidiano. Es 3-regular con 16 vértices.
• El Grafo de Papo es el gráfico de Levi del Pappus configuration, compuesto por 9 puntos y 9 líneas. Al igual que la configuración de Desargues, hay 3 puntos en cada línea y 3 líneas que pasan por cada punto. Es 3-regular con 18 vértices.
• El Gray graph es el gráfico de Levi de una configuración que se puede realizar en $\mathbb {R} ^{3}$ como una cuadrícula $3\times 3\times 3$ de 27 puntos y las 27 líneas ortogonales que los atraviesan.
• El Grafo de Tutte-Coxeter es el gráfico de Levi del Cremona–Richmond configuration. También se conoce como jaula (3,8) y es 3 regular con 30 vértices.
• El grafo hipercubo de cuatro dimensiones $Q_{4}$ es el gráfico de Levi del Möbius configuration formado por los puntos y planos de dos tetraedros mutuamente incidentes.
• El Ljubljana graph en 112 vértices es el gráfico de Levi de la configuración de Ljubljana.​

Enlaces externos

• Weisstein, Eric W. «Levi Graph». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 

• Datos: Q6535569