Connected graphs with prescribed median and periphery (Q1126202)

The median (resp. periphery) is the set of vertices of a graph \(G\) minimizing (resp. maximizing) the sum of (resp. largest) distances to all other vertices. The radius \(r(G)\) is the minimum of such largest distances. Three structural theorems are shown. First, any graph is the median of some graph of diameter 2. Second, two graphs \(F\) and \(G\) are the median and periphery of some graph in which they lie at distance \(m\) iff \(m<r(G)\) and \(F\) is complete when \(r(G)=2\). Third, a complete characterization is obtained for those triplets of graphs \(F\), \(G\) and \(K\) for which some graph exists having \(F\) as median, \(G\) as periphery and \(K\) as intersection of these.