# Modular graph

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Modular_graph
> Markdown URL: https://mediated.wiki/source/Modular_graph.md
> Source: https://en.wikipedia.org/wiki/Modular_graph
> Source revision: 1167017433
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Mathematical graph with at least one median per triple of vertices

Not to be confused with [Modular decomposition](/source/Modular_decomposition) or [Modularity (networks)](/source/Modularity_(networks)).

A modular graph derived from a [modular lattice](/source/Modular_lattice)

In [graph theory](/source/Graph_theory), a branch of mathematics, the **modular graphs** are [undirected graphs](/source/Undirected_graph) in which every three [vertices](/source/Vertex_(graph_theory)) x, y, and z have at least one *median vertex* *m*(*x*, *y*, *z*) that belongs to [shortest paths](/source/Shortest_path) between each pair of x, y, and z.[1] Their name comes from the fact that a finite [lattice](/source/Lattice_(order)) is a [modular lattice](/source/Modular_lattice) if and only if its [Hasse diagram](/source/Hasse_diagram) is a modular graph.[2]

It is not possible for a modular graph to contain a cycle of odd length. For, if C is a shortest odd cycle in a graph, x is a vertex of C, and yz is the edge of C farthest from x, there could be no median *m*(*x*, *y*, *z*). In this case, the only vertices on the shortest path yz are y and z themselves. Neither can belong to a shortest path from x to the other without shortcutting C and creating a shorter odd cycle. Because they have no odd cycles, every modular graph is a [bipartite graph](/source/Bipartite_graph).[1]

The modular graphs contain as a special case the [median graphs](/source/Median_graph), in which every triple of vertices has a unique median;[1] median graphs are related to [distributive lattices](/source/Distributive_lattice) 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](/source/Complete_bipartite_graph) 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] Every [chordal bipartite graph](/source/Chordal_bipartite_graph) (a class of graphs that includes the complete bipartite graphs and the bipartite [distance-hereditary graphs](/source/Distance-hereditary_graph)) is modular.[1]

## References

1. ^ [***a***](#cite_ref-isgci_1-0) [***b***](#cite_ref-isgci_1-1) [***c***](#cite_ref-isgci_1-2) [***d***](#cite_ref-isgci_1-3) [Modular graphs](http://www.graphclasses.org/classes/gc_50.html), Information System on Graph Classes and their Inclusions, retrieved 2016-09-30.

1. ^ [***a***](#cite_ref-arb_2-0) [***b***](#cite_ref-arb_2-1) Bandelt, H.-J.; Dählmann, A.; Schütte, H. (1987), "Absolute retracts of bipartite graphs", *[Discrete Applied Mathematics](/source/Discrete_Applied_Mathematics)*, **16** (3): 191–215, [doi](/source/Doi_(identifier)):[10.1016/0166-218X(87)90058-8](https://doi.org/10.1016%2F0166-218X%2887%2990058-8), [MR](/source/MR_(identifier)) [0878021](https://mathscinet.ams.org/mathscinet-getitem?mr=0878021).

---
Adapted from the Wikipedia article [Modular graph](https://en.wikipedia.org/wiki/Modular_graph) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Modular_graph?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.