On a generalization of median graphs: $k$-median graphs

Abstract

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\le i\le 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.