Gráfico modular

En la 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 un retículo finito es un retículo 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. Pues, si C es el 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 existir 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 de ellos 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, todo grafo modular es un grafo bipartito . ^{[ 1 ]}

Los grafos modulares contienen como caso especial los grafos medianos , en los que cada triplete 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 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 ]}