On graphs with prescribed median I

The distance of a vertex u in a connected graph H is the sum of all the distances from u to the other vertices of H. The median M(H) of H is the subgraph of H induced by the vertices of minimum distance. For any graph G , let f(G) denote the minimum order of a connected graph H satisfying M(H) ≅ G. It is shown that if G has n vertices and minimum degree δ then f(G) ⩽ 2 n − δ + 1. Graphs having both median and center prescribed are constructed. It is also shown that if the vertices of a K r are removed from a graph H , then at most r components of the resulting graph contain median vertices of H .