Modular graph
In graph theory, a branch of mathematics, the modular graphs are graphs in which every three vertices x, y, and z have a median vertex m(x,y,z) that belongs to shortest paths between each pair of x, y, and z.[1] Their name comes from the fact that a lattice is a modular lattice if and only if its Hasse diagram is a modular graph.[2]
It is not possible for a modular graph to contain a cycle of odd length. For, in such a case, if C is a shortest odd cycle, x is a vertex of C, and yz is the edge of the cycle farthest from x, there could be no median m(x,y,z), for the paths from the median to y and z and the edge yz would together form a shorter odd cycle. Therefore, every modular graph is a bipartite graph.[1]
The modular graphs contain as a special case the median graphs, in which every triple of vertices has a unique median;[1] median graphs are related to distributive lattices in the same way that modular graphs are related to modular lattices. However, the modular graphs also include other graphs such as the complete bipartite graphs where the medians are not unique: when the three vertices x, y, and z all belong to one side of the bipartition of a complete bipartite graph, every vertex on the other side is a median.[2]
References
- ^ a b c Modular graphs, Information System on Graph Classes and their Inclusions, retrieved 2016-09-30.
- ^ a b Bandelt, H.-J.; Dählmann, A.; Schütte, H. (1987), "Absolute retracts of bipartite graphs", Discrete Applied Mathematics, 16 (3): 191–215, doi:10.1016/0166-218X(87)90058-8, MR 0878021.