graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, a branch of mathematics, the modular graphs are

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

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 tw ...

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 Lattice may refer to: Arts and design * Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material * Lattice (music), an organized grid model of pitch ratios * Lattice (pastry), an ornam ...

is a

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

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, ≤)'' one represents ea ...

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 , for the only vertices on the shortest path are and themselves, but neither can belong to a shortest path from to the other without shortcutting and creating a shorter odd cycle. Therefore, every modular graph is a

bipartite graph In the mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...

. 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 vertices ''a'', ''b'', and ''c'' have a unique ''median'': a vertex ''m''(''a'',''b'',''c'') that belongs to shortest paths between each pair o ...

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 in which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set uni ...

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 In the mathematical area of graph theory, a chordal bipartite graph is a bipartite graph ''B'' = (''X'',''Y'',''E'') in which every cycle of length at least 6 in ''B'' has a ''chord'', i.e., an edge that connects two vertices that are a d ...

(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 distances in any connected induced subgraph are the same as they are in the original graph. Thus, any ...

s) is modular.

References

{{reflist Graph families Bipartite graphs