Graphs with connected medians (Q2784516)

For a nonnegative weight function \(\pi\) on vertices \(u\) of a finite connected graph \(G\), let NEWLINE\[NEWLINEF_{\pi} (x)=\sum_u \pi(u) d(u,x)NEWLINE\]NEWLINE where \(d\) denotes the distance. The median set consists of all vertices \(x\) which give a minimum of \(F_{\pi} (x)\). A local median is a vertex which gives a lower value of \(F_{\pi}(x)\) than any of its neighbors. This paper proves that the median set is connected for all \(\pi\) if and only if the median set always equals the local median set, if and only if any two vertices can be connected by a path along which \(F_{\pi}\) is peakless, as well as several other conditions. These are equivalent to a local condition which can be tested in polynomial time. These conditions are refined so that they can be applied to specific classes like the class of Helly graphs (it is proved that all Helly graphs satisfy them).