graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, a branch of mathematics, the modular graphs are

undirected graph In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...

s in which every three vertices , , and have at least one ''median vertex'' that belongs to

shortest path In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized. The problem of finding the shortest path between two ...

s between each pair of , , and .Modular graphs
Information System on Graph Classes and their Inclusions, retrieved 2016-09-30. Their name comes from the fact that a finite lattice is a

modular lattice In the branch of mathematics called order theory, a modular lattice is a lattice that satisfies the following self- dual condition, ;Modular law: implies where are arbitrary elements in the lattice, ≤ is the partial order, and & ...

if and only if its

Hasse diagram In order theory, a Hasse diagram (; ) is a type of mathematical diagram used to represent a finite partially ordered set, in the form of a drawing of its transitive reduction. Concretely, for a partially ordered set (S,\le) one represents each ...

is a modular graph.. It is not possible for a modular graph to contain a cycle of odd length. For, if is a shortest odd cycle in a graph, is a vertex of , and is the edge of farthest from , there could be no median . In this case, the only vertices on the shortest path are and themselves. Neither can belong to a shortest path from to the other without shortcutting and creating a shorter odd cycle. Because they have no odd cycles, every modular graph is a

bipartite graph In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...

. The modular graphs contain as a special case the

median graph In graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertex (graph theory), vertices ''a'', ''b'', and ''c'' have a unique ''median'': a vertex ''m''(''a'',''b'',''c'') that belongs to shortest pat ...

s, in which every triple of vertices has a unique median; median graphs are related to

distributive lattice In mathematics, a distributive lattice is a lattice (order), lattice in which the operations of join and meet distributivity, distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice o ...

s 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 graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory ...

s where the medians are not unique: when the three vertices , , and all belong to one side of the bipartition of a complete bipartite graph, every vertex on the other side is a median. Every chordal bipartite graph (a class of graphs that includes the complete bipartite graphs and the bipartite

distance-hereditary graph In graph theory, a branch of discrete mathematics, a distance-hereditary graph (also called a completely separable graph) is a graph in which the Distance (graph theory), distances in any connected graph, connected induced subgraph are the same as ...

s) is modular.

References

{{reflist Graph families Bipartite graphs