On the remoteness function in median graphs

A profile on a graph GG is any nonempty multiset whose elements are vertices from GG. The corresponding remoteness function associates to each vertex x∈V(G)x∈V(G) the sum of distances from xx to the vertices in the profile. Starting from some nice and useful properties of the remoteness function in hypercubes, the remoteness function is studied in arbitrary median graphs with respect to their isometric embeddings in hypercubes. In particular, a relation between the vertices in a median graph GG whose remoteness function is maximum (antimedian set of GG) with the antimedian set of the host hypercube is found. While for odd profiles the antimedian set is an independent set that lies in the strict boundary of a median graph, there exist median graphs in which special even profiles yield a constant remoteness function. We characterize such median graphs in two ways: as the graphs whose periphery transversal number is 2, and as the graphs with the geodetic number equal to 2. Finally, we present an algorithm that, given a graph GG on nn vertices and mm edges, decides in O(mlogn)O(mlogn) time whether GG is a median graph with geodetic number 2.