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 una celosía finita es una celosía modular si y solo si su diagrama de Hassees un gráfico modular. [2]
No es posible que un gráfico modular contenga un ciclo de longitud impar. Porque, si C es un ciclo impar más corto en una gráfica, x es un vértice de C , e yz es el borde del ciclo más alejado de x , no podría haber una mediana m ( x , y , z ) , para los únicos vértices en el camino más corto yz están y y z ellos mismos, pero ninguno puede pertenecer a un camino más corto de xa el otro sin atajar C y crear un ciclo impar más corto. Por lo tanto, todo gráfico modular es un gráfico bipartito . [1]
Los gráficos modulares contienen como caso especial los gráficos de mediana , en los que cada triple de vértices tiene una mediana única; [1] Las gráficas medianas están relacionadas con las celosías distributivas de la misma manera que las gráficas modulares están relacionadas con las celosías modulares. Sin embargo, las gráficas modulares también incluyen otras gráficas como las gráficas bipartitas completas donde las medianas no son únicas: cuando los tres vértices x , y , yz pertenecen todos a un lado de la bipartición de una gráfica bipartita completa, cada vértice en el el otro lado es una mediana. [2] Cada grafo bipartito cordal (una clase de grafos que incluye los grafos bipartitos completos y los grafos hereditarios de distancia bipartitos ) es modular. [1]
Referencias
- ^ a b c d Gráficos modulares , Sistema de información sobre clases de gráficos y sus inclusiones, consultado el 30 de septiembre de 2016.
- ↑ a b Bandelt, H.-J .; Dählmann, A .; Schütte, H. (1987), "Retracciones absolutas de gráficos bipartitos", Matemáticas aplicadas discretas , 16 (3): 191-215, doi : 10.1016 / 0166-218X (87) 90058-8 , MR 0878021.