  Median graphs are connected graphs in which for all three vertices there is a
unique vertex that belongs to shortest paths between each pair of these three
vertices. To be more formal, a graph $G$ is a median graph if, for all $\mu,
u,v\in V(G)$, it holds that $|I(\mu,u)\cap I(\mu,v)\cap I(u,v)|=1$ where
$I(x,y)$ denotes the set of all vertices that lie on shortest paths connecting
$x$ and $y$. In this paper we are interested in a natural generalization of
median graphs, called $k$-median graphs. A graph $G$ is a $k$-median graph, if
there are $k$ vertices $\mu_1,\dots,\mu_k\in V(G)$ such that, for all $u,v\in
V(G)$, it holds that $|I(\mu_i,u)\cap I(\mu_i,v)\cap I(u,v)|=1$, $1\leq i\leq
k$. By definition, every median graph with $n$ vertices is an $n$-median graph.
We provide several characterizations of $k$-median graphs that, in turn, are
used to provide many novel characterizations of median graphs.
