Call a graph vertex a median of a graph if it lies on all shortest paths between each pair of vertices , , and in . A median graph is then defined as a simple graph in which every three vertices possess a unique median.
A connected graph is a median graph iff it is an induced graph of an hypercube graph such that for any three vertices of their median in the hypercube graph is also a vertex of (Mulder 1978, Munarini 2019).
The numbers of median graphs on , 2, ... vertices are 1, 1, 1, 3, 4, 11, 23, 69, 178, 567, ... (OEIS A292623), the first few of which are illustrated above.
The graph Cartesian product of two median graphs is a median graph.
Trees are median graphs, so path and star graphs are as well.
Grid graphs (of all dimensions) are median graphs, so ladder graphs are as well.
Other classes of graphs that are median include book , Fibonacci cube, gear (for ), hypercube, and stacked book graphs.