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.
