Grafo de Levi

Grafo de Levi
El grafo de Papo, un grafo de Levi con 18 vértices, formado a partir de la configuración de Papo. Los vértices etiquetados con letras individuales corresponden a puntos de la configuración; los vértices etiquetados con tres letras corresponden a líneas que pasan por tres puntos.
Cintura	≥ 6

En combinatoria, un grafo de Levi o grafo de incidencia es un grafo bipartito asociado con una estructura de incidencia.​​ A partir de una colección de puntos y líneas en una geometría de incidencia o una configuración proyectiva, se configura un grafo 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 del matemático alemán Friedrich Wilhelm Levi (1888-1966), quien escribió sobre ellos en 1942.​​

Propiedades

El grafo de Levi de un sistema de puntos y líneas generalmente tiene cintura con un valor de al menos seis: cualquier 4-ciclo correspondería a dos rectas que pasan por los mismos dos puntos. Por el contrario, cualquier grafo bipartito con una cintura de al menos seis puede verse como el grafo de Levi de una estructura de incidencia abstracta. Los grafos de configuraciones de Levi​ son birregulares, y cada grafo birregular con una cintura de al menos seis puede verse como el grafo de Levi de una configuración abstracta.​

Los grafos de Levi también se pueden definir para otros tipos de estructura de incidencia, como las incidencias entre puntos y planos en el espacio euclídeo. Para cada grafo de Levi, existe un hipergrafo equivalente y viceversa.

Ejemplos

Grafo de Heawood y plano de Fano
Los vértices 3 son parte del contorno circular (3, 5, 6), la arista diagonal (3, 7, 4), y la arista lateral (1, 3, 2).

• El grafo de Desargues es el grafo de Levi de una configuración de Desargues, compuesta por 10 puntos y 10 líneas. Hay 3 puntos en cada línea y 3 líneas que pasan por cada punto. El grafo de Desargues también se puede ver como un grafo de Petersen generalizado G(10,3) o un grafo de Kneser bipartito con parámetros 5,2. Es 3-regular, con 20 vértices.
• El grafo de Heawood es el grafo de Levi del plano de Fano. También se conoce como una (3,6)-jaula y es 3-regular, con 14 vértices.
• El grafo de Möbius-Kantor es el grafo de Levi de la configuración de Möbius-Kantor, un sistema de 8 puntos y 8 rectas que no se puede realizar mediante rectas en el plano euclídeo. Es 3-regular, con 16 vértices.
• El grafo de Papo es el grafo de Levi de la configuración de Papo, 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 grafo de Gray es el grafo de Levi de una configuración que se puede realizar en $\mathbb {R} ^{3}$ como una cuadrícula de $3\times 3\times 3$ con 27 puntos y las 27 líneas ortogonales que los atraviesan.
• El grafo de Tutte-Coxeter es el grafo de Levi de la configuración de Cremona-Richmond. También se conoce como (3,8)-jaula y es 3 regular, con 30 vértices.
• El grafo hipercubo de cuatro dimensiones $Q_{4}$ es el grafo de Levi de la configuración de Möbius formado por los puntos y planos de dos tetraedros mutuamente incidentes.
• El grafo de Ljubljana es el grafo de Levi de la configuración de Ljubljana, que cuenta con en 112 vértices.​

Véase también

• Incidencia (geometría)
• Estructura de incidencia ‎

Enlaces externos

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

• Datos: Q6535569