| dc.description.abstract |
A profile on a graph G is any nonempty multiset whose elements are vertices from G.
The corresponding remoteness function associates to each vertex x 2 V.G/ the sum of
distances from x 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 G whose remoteness function is maximum
(antimedian set of G) 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 G on n vertices and m edges, decides in O.mlog n/
time whether G is a median graph with geodetic number 2 |
en_US |