Gráfico modular

En teoría de grafos , una rama de las matemáticas, los grafos modulares son grafos no dirigidos en los que cada tres vértices x , y y z tienen al menos un vértice mediano m ( x , y , z ) que pertenece a los caminos más cortos entre cada par de x , y y z . ^[1] Su nombre proviene del hecho de que una red finita es una red modular si y solo si su diagrama de Hasse es un grafo modular. ^[2]

No es posible que un grafo modular contenga un ciclo de longitud impar. Porque, si C es un ciclo impar más corto en un grafo, x es un vértice de C , e yz es la arista de C más alejada de x , no podría haber una mediana m ( x , y , z ) . En este caso, los únicos vértices en el camino más corto yz son y y z . Ninguno puede pertenecer a un camino más corto de x al otro sin acortar C y crear un ciclo impar más corto. Debido a que no tienen ciclos impares, cada grafo modular es un grafo bipartito . ^[1]

Los grafos modulares contienen como caso especial los grafos medianos , en los que cada triple de vértices tiene una mediana única; ^[1] los grafos medianos están relacionados con los retículos distributivos de la misma manera que los grafos modulares están relacionados con los retículos modulares. Sin embargo, los grafos modulares también incluyen otros grafos como los grafos bipartitos completos donde las medianas no son únicas: cuando los tres vértices x , y y z pertenecen todos a un lado de la bipartición de un grafo bipartito completo, cada vértice del otro lado es una mediana. ^[2] Todo grafo bipartito cordal (una clase de grafos que incluye los grafos bipartitos completos y los grafos bipartitos hereditarios de distancia ) es modular. ^[1]