En teoría de grafos , particularmente en la teoría de hipergrafos , el grafo lineal de un hipergrafo H , denotado L( H ) , es el grafo cuyo conjunto de vértices es el conjunto de las hiperaristas de H , con dos vértices adyacentes en L( H ) cuando sus hiperaristas correspondientes tienen una intersección no vacía en H. En otras palabras, L( H ) es el grafo de intersección de una familia de conjuntos finitos . Es una generalización del grafo lineal de un grafo .
Las preguntas sobre los grafos lineales de los hipergrafos son a menudo generalizaciones de preguntas sobre los grafos lineales de los grafos. Por ejemplo, un hipergrafo cuyas aristas tienen todas un tamaño k se llama k -uniforme . (Un hipergrafo 2-uniforme es un grafo). En la teoría de los hipergrafos, a menudo es natural exigir que los hipergrafos sean k -uniformes . Todo grafo es el grafo lineal de algún hipergrafo, pero, dado un tamaño de arista fijo k , no todo grafo es un grafo lineal de algún hipergrafo k -uniforme . Un problema principal es caracterizar aquellos que lo son, para cada k ≥ 3 .
Un hipergrafo es lineal si cada par de hiperaristas se interseca en un vértice como máximo. Todo grafo es el grafo lineal, no sólo de algún hipergrafo, sino de algún hipergrafo lineal. [1]
Beineke [2] caracterizó los gráficos lineales de los grafos mediante una lista de 9 subgrafos inducidos prohibidos . (Véase el artículo sobre grafos lineales ). No se conoce ninguna caracterización mediante subgrafos inducidos prohibidos de los grafos lineales de hipergrafos k-uniformes para cualquier k ≥ 3, y Lovász [3] demostró que no existe tal caracterización mediante una lista finita si k = 3.
Krausz [4] caracterizó los gráficos lineales de los grafos en términos de coberturas de clique . (Ver Gráficos lineales ). Berge [5] proporcionó una caracterización global del tipo Krausz para los gráficos lineales de hipergrafos k -uniformes para cualquier k ≥ 3.
Naik, Rao, Shrikhande y Singhi [6] dieron una caracterización global del tipo Krausz para los grafos lineales de hipergrafos lineales k -uniformes para cualquier k ≥ 3. Al mismo tiempo, encontraron una lista finita de subgrafos inducidos prohibidos para hipergrafos lineales 3-uniformes con un grado de vértice mínimo de al menos 69. Metelsky|l y Tyshkevich [7] y Jacobson, Kézdy y Lehel [8] mejoraron este límite a 19. Por último, Skums, Suzdal' y Tyshkevich [9] redujeron este límite a 16. Metelsky y Tyshkevich [10] también demostraron que, si k > 3, no existe tal lista finita para hipergrafos lineales k -uniformes, sin importar qué límite inferior se coloque en el grado.
La dificultad para encontrar una caracterización de hipergrafos lineales k -uniformes se debe al hecho de que hay infinitos subgrafos inducidos prohibidos. Para dar ejemplos, para m > 0, considere una cadena de m grafos de rombos tales que los rombos consecutivos comparten vértices de grado dos. Para k ≥ 3, agregue aristas colgantes en cada vértice de grado 2 o 4 para obtener una de las familias de subgrafos prohibidos mínimos de Naik, Rao, Shrikhande y Singhi [11] como se muestra aquí. Esto no descarta ni la existencia de un reconocimiento polinomial ni la posibilidad de una caracterización de subgrafos inducidos prohibidos similar a la de Beineke de grafos lineales de grafos.
Hay algunas caracterizaciones interesantes disponibles para gráficos de líneas de hipergrafos lineales k -uniformes debido a varios autores [12] bajo restricciones en el grado mínimo o el grado mínimo del borde de G. El grado mínimo del borde al menos k 3 -2 k 2 +1 en Naik, Rao, Shrikhande y Singhi [13] se reduce a 2 k 2 -3 k +1 en Jacobson, Kézdy y Lehel [14] y Zverovich [15] para caracterizar gráficos de líneas de hipergrafos lineales k -uniformes para cualquier k ≥ 3.
No se conoce la complejidad de reconocer gráficos de líneas de hipergrafos lineales k -uniformes sin ninguna restricción en el grado mínimo (o grado mínimo de arista). Para k = 3 y un grado mínimo de al menos 19, el reconocimiento es posible en tiempo polinomial. [16] Skums, Suzdal' y Tyshkevich [17] redujeron el grado mínimo a 10.
Hay muchos problemas abiertos y conjeturas interesantes en Naik et al., Jacoboson et al., Metelsky et al. y Zverovich.
El grafo de disjunción de un hipergrafo H , denotado D( H ), es el grafo cuyo conjunto de vértices es el conjunto de las hiperaristas de H , con dos vértices adyacentes en D( H ) cuando sus hiperaristas correspondientes son disjuntas en H . [18] En otras palabras, D( H ) es el grafo complementario de L( H ). Una camarilla en D( H ) corresponde a un conjunto independiente en L( H ), y viceversa.